软件工程第三次个人作业

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

软件工程第三次作业

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.解题思路

分治法
递推法

3.源代码

思路分析：对于数组array，从array[1]开始逐个进行相加，与最大值比较，并不停地更替最大值
代码实现：

#include <iostream>
#include <stdlib.h>
using namespace std;
int GreatestSumOfSubArray(int array[],int n)
{
    int t = 0,i;
    for (i = 0; i < n; i++)
    {
        if (array[i] < 0)
            t++;
    }
    if (t == n) return 0;
    if (n <= 0)return 0;
    int result,sum ;                                   
    result = sum = array[0];
    for (int i = 1; i <= n; i++) 
    {
        if (sum < 0)                                  
            sum = 0;
        sum += array[i];
        if (sum > result)
            result = sum;
    }
    return result;
}
int main()
{
    int a[20],i=0,n;
    cin >> n;
    cout<<endl;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << GreatestSumOfSubArray(a,n) << endl;
    return 0;
}

4.判定条件覆盖

流程图：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
判断/条件覆盖测试
判定一：n=0,n!=0;
判定二：i<n,i>=n;
判定三：sum<0,sum>=0;
判定四：sum>result,sum<=result;
测试代码

#include "stdafx.h"
#include "CppUnitTest.h"
using namespace Microsoft::VisualStudio::CppUnitTestFramework
namespace UnitTest1
{       
    TEST_CLASS(UnitTest1)
    {
    public:
        
        TEST_METHOD(TestMethod1)
        {
            // TODO: 在此输入测试代码
            int  result, a[5] = { -1,-2,-3,-4,-5 };
            result = GreastestSumOfSubArray(a, 5);
            Assert ::AreEqual(result, 0);
        }

        TEST_METHOD(TestMethod2)
        {
            // TODO: 在此输入测试代码
            int  result, a[5] = { 1,2,3,4,5 };
            result = GreastestSumOfSubArray(a, 5);
            Assert ::AreEqual(result, 15);
        }

        TEST_METHOD(TestMethod3)
        {
            // TODO: 在此输入测试代码
            int  result, a[5] = { -1,2,4,-5,11 };
            result = GreastestSumOfSubArray(a, 5);
            Assert ::AreEqual(result, 12);
        }

        TEST_METHOD(TestMethod4)
        {
            // TODO: 在此输入测试代码
            int  result, a[6] = { 2,3,-6,7,-2,9 };
            result = GreastestSumOfSubArray(a, 6);
            Assert ::AreEqual(result, 14);
        }
    };
}

5.测试结果

测试样例：
a[5]={-1,-2,-3,-4,-5}
a[5]={1,2,3,4,5}
a[5]={-1,2,4,-5,11}
a[6]={2,3,-6,,7,-2,9}
测试结果：
coding代码地址：
https://git.dev.tencent.com/little-sunshine/ruanjiangongchengdisanciboke.git