第三次作业

一、题目的选择：

我选择的题目为题目一：最大连续子数组和（最大子段和）
给定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。

二、代码的编写：

我脑子里第一个想法就是对数组内每一个数A[i]进行遍历，然后遍历以它们为起点的子数组，比较各个子数组的大小，找到最大连续子数组。
话不多说，编写代码

#include <stdio.h>
int main()
{
	int A[6] = { -2, 11, -4, 13, -5, -2 };
	int array_length = sizeof(A) / sizeof(A[0]);//数组大小
	int sum = -10000;//记录子数组的和
	for (int i = 0; i < array_length; i++)
	{
		for (int j = i; j < array_length; j++)
		{
			int subarraysum = 0;//所遍历出来的子数组的和
			//计算遍历的子数组之和
			for (int k = i; k <= j; k++)
			{
				subarraysum += A[k];
			}
			//找出最大的子数组
			if (subarraysum>sum)
			{
				sum = subarraysum;
			}
		}
	}
	printf("最大子段和为 %d",sum);//将结果打印出来
	getchar();
	return 0;
}

此程序每一次都从i到j地重新计算一次，用了三层循环，此程序的时间复杂度为O（n3），虽然好理解但是比较复杂

三、运行结果

对（a[1],a[2],a[3],a[4],a[5],a[6]）=(-2,11,-4,13,-5,-2)进行测试，其最大子段和为20

四、单元测试

单元测试的方式有
（1）语句覆盖：使得程序中每个语句至少都能被执行一次。
（2）判定覆盖：使得程序中每个判定至少为T和F各一次。
（3）条件覆盖：使得判定中的每个条件获得各种可能的结果。
（4）判定/条件覆盖：同时满足判定覆盖和条件覆盖。
（5）条件组合覆盖：使得每个判定中条件的各种可能组合都至少出现一次。
我选择的是判定条件覆盖。
测试用例：
样例1:a[3]={1,2,3}结果为6
样例2:a[4]={-1，2，-4,2}结果为2
样例3:a[3]={-1，-2，-3}结果为0
样例4:a[6]={-2,11，-4,13，-5，-2}结果为20

单元测试所用代码如下

#include "stdafx.h"
#include "CppUnitTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 100
int maxsub(int left, int right,int a[])
{
    int center, i;
    int sum, left_sum, right_sum;
    int left_max, right_max;
    center = (left + right) / 2;
    if (left == right)
        return a[left]>0 ? a[left] : 0;
    else
    {
        left_sum = maxsub(left, center,a);
        right_sum = maxsub(center + 1, right,a);
        sum = 0;
        left_max = 0;
        for (i = center; i >= left; i--)
        {
            sum += a[i];
            if (sum>left_max)
                left_max = sum;
        }
        sum = 0;
        right_max = 0;
        for (i = center + 1; i <= right; i++)
        {
            sum += a[i];
            if (sum>right_max)
                right_max = sum;
        }
        sum = right_max + left_max;
        if (sum<left_sum)
            sum = left_sum;
        if (sum<right_sum)
            sum = right_sum;
    }
    return sum;
}
namespace UnitTest1
{       
    TEST_CLASS(UnitTest1)
    {
    public:
        
        TEST_METHOD(TestMethod1)
        {
            // TODO:  在此输入测试代码
            int a[6] = { -1,-6,-3,-5,-7,-2 };
            int sum = maxsub(0, 5,a);
            Assert::AreEqual(0, sum);
        }
        TEST_METHOD(TestMethod2)
        {
            // TODO:  在此输入测试代码
            int a[6] = { -3,5,-8,9,-2,6 };
            int sum = maxsub(0, 5, a);
            Assert::AreEqual(13, sum);
        }
        TEST_METHOD(TestMethod3)
        {
            // TODO:  在此输入测试代码
            int a[6] = { 8,-3,5,6,-9,7 };
            int sum = maxsub(0, 5, a);
            Assert::AreEqual(16, sum);
        }
    };
}

五、心得体会

本次作业照上次作业的难度有所提升，但是只要静下心来安心弄很容易就弄出来了。
所以说正是世上无难事