题目

最大连续子数组和（最大子段和）

背景

问题： 给定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。
-- 引用自《百度百科》

解决方法

递推法：在对于上述分治算法的分析中我们注意到，若记b[j]=max(a[i]+a[i+1]+..+a[j]),其中1<=i<=j,并且i<=j<=n。
则所求的最大子段和为max b[j]，1<=j<=n。由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的递推方程为:
b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n

代码地址

https://dev.tencent.com/u/yang_gang/p/ruanjiangongchengdisancizuoye/git

流程图分析

代码实现

代码如下

#include <iostream>
#include "text.h"
using namespace std;

class myclass {
public:
    myclass(int n) { i = n; };
    void input();
    int max();
    int a[100], i;

};

void myclass::input() {
    int j = 0;
    for (j; j < i; j++) {
        cin >> a[j];
    }

};

int myclass::max() {
    int b[100];
    int max1;
    int j;
    b[0] = a[0];
    max1 = b[0];
    for (j = 1; j < i; j++) {
        if (b[j - 1] > 0) { b[j] = a[j] + b[j - 1]; }
        else b[j] = a[j];
        if (b[j] > max1) max1 = b[j];

    }
    if (max1 < 0) return max1 = 0;
    else return max1;

};

void main() {
    int i, max;
    cin >> i;
    myclass a(i);
    a.input();
    max = a.max();
    cout << max;
    while(1);
}

测试用例方法

采用条件覆盖的方法。
应满足以下覆盖情况：
判定一：n>0,n<=0
判定二：b[j]>0,b[j-1]<=0
判定三：max>b[j],max<=b[j]
判定四：j>i,J<=i
判定五：max>0,max<=0
设计如下测试用例
(1)没有数，max=0;
(2)全是负数，-2，-2，-4，-3，-5，-2，max=0;
(3)一般情况，-2, 11, -4, 13, -5, -2， max=20;
(4)全是正数，2，2，4，3，5，2 max=18;
代码如下

       TEST_CLASS(UnitTest1)
    {
    public:
        
        TEST_METHOD(TestMethod1)
        {  // 一般情况
            myclass test(6);
            test.a[0] = -2;
            test.a[1] = 11;
            test.a[2] = -4;
            test.a[3] = 13;
            test.a[4] = -5;
            test.a[5] = -2;
            Assert::AreEqual(test.max(), 20);
        };
        TEST_METHOD(TestMethod2)
        {//没有数
            myclass test(0);
            Assert::AreEqual(test.max(), 0);
        };
        TEST_METHOD(TestMethod3)
        {//全是负数
            myclass test(6);
            test.a[0] = -2;
            test.a[1] = -2;
            test.a[2] = -4;
            test.a[3] = -3;
            test.a[4] = -5;
            test.a[5] = -2;
            Assert::AreEqual(test.max(), 0);
        };
        TEST_METHOD(TestMethod4)
        {//全是正数
            myclass test(6);
            test.a[0] = 2;
            test.a[1] = 2;
            test.a[2] = 4;
            test.a[3] = 3;
            test.a[4] = 5;
            test.a[5] = 2;
            Assert::AreEqual(test.max(), 18);
        };

    };
 

测试结果