最大子段和求解与测试

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

最大子段和

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。
【输入形式】n个整数数值
【输出形式】最大子段和的数值
【样例输入】-2 11 -4 13 -5 -2
【样例输出】20

2. 程序设计

在设计程序的过程中使用可变长度的vector存储输入的数据，其中输入数据的长度可用size()方法获得。对于求解问题的算法这里采用了递推法。

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

算法流程图如下
源代码

///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;
}

3. 选择覆盖标准及设计测试用例

选择条件/判定覆盖标准测试程序。

条件/判定条件/判定
判定一：size < 0
判定二：size > 0, temp > 0, temp > max, max > 0
判定三：size > 0, temp < 0, temp < max, max < 0

用例序号	用例	结果
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

4. 单元测试

单元测试所使用的代码以及测试结果如下。

单元测试代码

#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));
        }
    };
}