【问题描述】给定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。
【输入形式】n个整数数值
【输出形式】最大子段和的数值
【样例输入】-2 11 -4 13 -5 -2
【样例输出】20
在设计程序的过程中使用可变长度的vector存储输入的数据，其中输入数据的长度可用size()方法获得。对于求解问题的算法这里采用了递推法。
算法流程图如下
源代码
///maxSub.h
#pragma once
#include "pch.h"
#include <vector>
using namespace std;
int maxSubSum(vector<int> num)
{
int size = num.size();
if (size == 0) return 0;
int max = num[0];
int temp = num[0];
for (int x = 1; x < size; x++){
if (temp > 0)
temp += num[x];
else
temp = num[x];
max = temp > max ? temp : max;
}
return (max >= 0 ? max : 0);
}///maxSub.cpp
#include "pch.h"
#include <iostream>
#include "maxSub.h"
#include <vector>
using namespace std;
int main()
{
vector <int> number;
int x = 0;
int temp;
cin >> temp;
number.push_back(temp);
while (cin.get() != '\n') {
cin >> temp;
number.push_back(temp);
x++;
}
std::cout << std::endl<<maxSubSum(number) << std::endl;
}选择条件/判定覆盖标准测试程序。
| 用例序号 | 用例 | 结果 |
|---|---|---|
| 1 | {} | 0 |
| 2 | {-5, -8, -6, -9} | 0 |
| 3 | {1, 7, -1, 3, 6, -12} | 16 |
| 4 | {1, 5, 7, 9, 0, 4, 5} | 31 |
| 5 | {-2, 11, -4, 13, -5, -2} | 20 |
单元测试所使用的代码以及测试结果如下。
#include "stdafx.h"
#include "CppUnitTest.h"
#include "../maxSub/maxSub.h"
using namespace Microsoft::VisualStudio::CppUnitTestFramework;
namespace maxSub_Test
{
TEST_CLASS(UnitTest1)
{
public:
TEST_METHOD(Test_1)
{
vector<int> num{};
int actual = 0 ;
Assert::AreEqual(actual, maxSubSum(num));
}
TEST_METHOD(Test_2)
{
vector<int> num{ -5, -8, -6, -9 };
int actual = 0;
Assert::AreEqual(actual, maxSubSum(num));
}
TEST_METHOD(Test_3)
{
vector<int> num{ 1,7, -1, 3, 6, -12 };
int actual = 16;
Assert::AreEqual(actual, maxSubSum(num));
}
TEST_METHOD(Test_4)
{
vector<int> num{ 1, 5, 7, 9, 0, 4, 5 };
int actual = 31;
Assert::AreEqual(actual, maxSubSum(num));
}
TEST_METHOD(Test_5)
{
vector<int> num{ -2,11,-4,13,-5 , -2};
int actual = 20;
Assert::AreEqual(actual, maxSubSum(num));
}
};
}
要设计出较好的测试用例有一定的难度，需要多加练习总结才能做到更好。
? 项目源代码地址
原文：https://www.cnblogs.com/leexin/p/10738708.html