最大字段和

佚名 6年前 (2019-04-17) 随笔 1841人围观抢沙发百度已收录

1.题目要求

·给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n，
例如，当（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

2.题目分析

·从头开始遍历序列中的所有元素，从序列的第一个正数开始求字段和，并用max变量（最大字段和记录变量）边比较边记录；
·当某段字段和值小于或等于0时，记录字段和的变量清零，从新开始计算一段字段和，并通过与max变量的比较，记录当前的最大字段和；
·在遍历该序列的同时，不断用上述方法，比较和记录最大字段和，并在最终输出结果。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

3.程序设计

[coding.net可运行完整代码地址]（https://git.dev.tencent.com/LiChaoshuai/zuidaziduanhe.git）


#include <stdlib.h>
#include <stdio.h>
int test(int num[], int n)
{
    if (num == NULL || n == 0)
    {
        return 0;
    }
    int  i = 0,flag;
    int max = 0;
    for (i = 0; i < n; )
    {
        if (num[i] <= 0)
            i++;
        else
        {
            max = num[i];
            flag = max;
            i++;
            for (; i < n;)
            {
                flag = num[i] + flag;
                if (flag > max)
                    max = flag;
                if (flag <= 0)
                    flag = 0;
                i++;
            }
        }
    }
    return max;
}

int main()
{
    int *num,max;
    int  n = 0, i = 0, j = 0;
    scanf_s("%d", &n);
    num = (int *)malloc(sizeof(int)*n);
    while (i < n)
    {
        scanf_s("%d", &num[i]);
        i++;
    }
    max=test(num, n);
    printf("%d", max);
    return 0;
}

4.代码流程图

·最大字段和程序流程图如图4.1所示：

图4.1

5.测试代码结果

5.1 判定/条件覆盖测试

条件①	②	③	④	⑤
num=NULL	i<n	num[i]<=0	flag>max	flag<=0
num!=NULL	i>=n	num[i]>0	flag<=max	flag>0

注：num为存储数字序列的数组，n为序列中数字个数，i用以遍历数组num，flag用以记录当前字段和，max用以记录最大字段和。

5.2 测试用例

·判断数字序列可能会影响最大字段和的所有可能性，根据判断条件覆盖，设计测试用例（重复条件只设一个测试用例）：

样例1：num[] = {0},n=0；
样例2：num[5] = {-1,-2,-3,-4,-5},n=5；
样例3：num[5] = {1,2,3,4,5},n=5；
样例4：num[5] = {5,-1,2,3,4},n=5；
样例5：num[5] = {1,2,-5,3,4},n=5。

5.3 测试代码


#include "stdafx.h"
#include "CppUnitTest.h"
#include "..\ConsoleApplication1\finding.h"
using namespace Microsoft::VisualStudio::CppUnitTestFramework;

namespace UnitTest1
{       
    TEST_CLASS(UnitTest1)
    {
    public:
        
        TEST_METHOD(TestMethod1)
        {
            int max, num[] = {0};
            max=finding(num, 0);
            Assert::AreEqual(max, 0);
        }
        TEST_METHOD(TestMethod2)
        {
            int max, num[5] = {-1,-2,-3,-4, -5 };
            max = finding(num, 5);
            Assert::AreEqual(max, 0);
        }
        TEST_METHOD(TestMethod3)
        {
            int max, num[5] = {1,2,3,4,5};
            max = finding(num, 5);
            Assert::AreEqual(max, 15);
        }
        TEST_METHOD(TestMethod4)
        {
            int max, num[5] = {5,-1,2,3,4};
            max = finding(num, 5);
            Assert::AreEqual(max, 13);
        }
        TEST_METHOD(TestMethod5)
        {
            int max, num[5] = {1,2,-5,3,4};
            max = finding(num, 5);
            Assert::AreEqual(max, 7);
        }
    };
}