要求：
1.要求程序必须能处理1000个元素；
2.每个元素是int32类型的，出现子数组之和大于整型表示的最大范围会出现什么情况；
3.输入一个整形数组，数组里有正数也有负数；
4.数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和；
5.求所有子数组的和的最大值。要求时间复杂度为O(n)。
思路：
就是用一个一维数组记录以每个元素为结尾的子序列的最大和，然后再扫描一遍这个数组，以获取最大值。
源代码：
#include<iostream>
#define N 1000
using namespace std;
int Compare(int Group[], int Length)
{
int MaxSum[N][2];
MaxSum[0][0] = MaxSum[0][1] = Group[0];
for (int i = 1; i < Length; i++)
{
MaxSum[i][0] = __max(MaxSum[i - 1][0], MaxSum[i - 1][1]);
MaxSum[i][1] = __max(MaxSum[i - 1][1] + Group[i], Group[i]);
}
return __max(MaxSum[Length - 1][0], MaxSum[Length - 1][1]);
}
int main()
{
int Number[N];
int length;
cout << "请输入一个整型数组：" << endl;
cin >> Number[0];
length = 1;
while (getchar() != ‘\n‘)
{
cin >> Number[length++];
}
cout << "该数组中的最大的子数组和为：";
cout << Compare(Number, length) << endl;
system("pause");
return 0;
}
总结：
通过大一学习的C语言基础我们学习了将子函数结构和在程序里面定义动态数组，于是在该程序中就使用了子函数和指针，通过define来定义数组的长度。刚开始程序做出来时无法运行，输入完数组后回车就会退出程序，最后通过再“return 0；”前加入“system("pause")”程序才得以良好运行。当我们输入数组里的值过大后，结果总是为“-858993460”。
运行截图：