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.问题分析

要求一个数组中的最大子段和，可以想到若记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。我在这个问题中采用了上面的递推法。

3.程序设计

#include
    
     #include
     
      int a[100];int summ(int a[], int n) {    int maxx = -100010;    int l, r, temp = 0;    int sum = 0;    if (n == 0) maxx = 0;    for (int i = 0;i < n;i++)    {        sum += a[i];        if (sum>maxx)        {            maxx = sum;            l = temp;            r = i;        }        if (sum<0)        {            sum = 0;            temp = i + 1;            if (i == n - 1)maxx = 0;        }    }    return maxx;}int main(){    int n,sum;    scanf("%d", &n);    for (int k = 0; k < n; k++)    {        scanf("%d", &a[k]);    }    sum = summ(a, n);    if (sum == 0) printf("最大子段和为0");    else printf("最大子段和为%d\n", sum);    return 0;}
     
    

初始代码提交至coding.net中：

4.程序流程图

5.单元测试

• 用判定/条件覆盖
  判定结果为 0/正数
  条件为数组 空/全正/全负/全为0/正负都有
• 测试用例
  (1)a[] = {0}, 最大子段和为0；
  (2)a[5] = {0, 0, 0, 0, 0}, 最大子段和为0；
  (3)a[5] = {-1, -2, -3, -4, -5}, 最大子段和为0；
  (4)a[5] = {1, 2, 3, 4, 5}, 最大子段和为15；
  (5)a[5] = {-1, 1, 2, 4, -5}, 最大子段和为7；
  (6)a[5] = {1, -3, -4, 5, 4},最大子段和为9。
• 测试代码

#include "stdafx.h"#include "CppUnitTest.h"#include "../Project/标头.h"using namespace Microsoft::VisualStudio::CppUnitTestFramework;namespace UnitTest{           TEST_CLASS(UnitTest1)    {    public:                TEST_METHOD(TestMethod1)        {            int a[] = { 0 };            Assert::AreEqual(summ(a,0), 0);        }        TEST_METHOD(TestMethod2)        {            int a[5] = { 0, 0, 0, 0, 0 };            Assert::AreEqual(summ(a,5), 0);        }        TEST_METHOD(TestMethod3)        {            int a[5] = { -1, -2, -3, -4, -5 };            Assert::AreEqual(summ(a,5), 0);        }        TEST_METHOD(TestMethod4)        {            int a[5] = { 1, 2, 3, 4, 5 };            Assert::AreEqual(summ(a,5), 15);        }        TEST_METHOD(TestMethod5)        {            int a[5] = { -1, 1, 2, 4, -5 };            Assert::AreEqual(summ(a,5), 7);        }        TEST_METHOD(TestMethod6)        {            int a[5] = { 1, -3, -4, 5, 4 };            Assert::AreEqual(summ(a,5), 9);        }    };}

• 测试结果

  

  6.遇到的问题及解决办法

  初始代码中我用的变量基本都是全局定义，运行代码能得到正确值，但是在单元测试中一直不成功，然后我又进一步改写代码把变量基本定义在函数内，从而解决了问题。

  7.总结

  通过这两次的单元测试作业，我懂得了变量的运用，掌握了单元测试基本要领，对VS2017运用的也更加的熟练。