软件工程作业-(third)

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

1.选题目(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.程序设计和代码

2.1GITHUB代码地址https://github.com/Lpofeng/find_max_add.git

2.2程序流程图

此次采用判定/条件覆盖

2.3核心代码

int find_max_add(vector<int> vec, const int size, int* start, int* end)
{
if (size == 0)
    return -100;
int final_max = vec[0]>0?vec[0]:0;
if (size != 1) {
    int cur_start = 0;
    int cur_end = 0;
    for (int i = 0; i < size; ++i) 
    {
        int cur_max = vec[i];
        cur_start = i;
        for (int j = i + 1; j < size; ++j)
        {
            cur_max += vec[j];
            if (cur_max > final_max)
            {
                final_max = cur_max;
                *start = cur_start;
                *end = j;
            }
        }
    }
    if (final_max < vec[size - 1])
    {
        final_max=vec[size - 1];
        *start = size - 1;
    }
}
return final_max;

}

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

3.测试代码

    TEST_METHOD(TestMethod1)
    {
        int s = 0;
        int e = 0;
        vector<int> v = { -2,-1,-3,5};
        Assert::AreEqual(5,find_max_add(v, 4, &s, &e));
    }
    TEST_METHOD(TestMethod2)
    {
        int s = 0;
        int e = 0;
        vector<int> v = {-3,-1,0,5,99,-150 };
        Assert::AreEqual(104, find_max_add(v, 6, &s, &e));
    }
    TEST_METHOD(TestMethod3)
    {
        int s = 0;
        int e = 0;
        vector<int> v = { -20,-1,30,5,-10,33,-49,-13 };
        Assert::AreEqual(58, find_max_add(v, 8, &s, &e));
    }
    TEST_METHOD(TestMethod4)
    {
        int s = 0;
        int e = 0;
        vector<int> v = { -41,-28,-0,-3,-5,-33,-44,0 };
        Assert::AreEqual(0, find_max_add(v, 8, &s, &e));
    }