其实题目很简单，但智障的我一开始弄错了，直接把所有负数提出去然后把剩下的相加，这也太简单了点吧。。。。后来想想，貌似不太对，于是，重来。一共用了三种方法。(名字都是我瞎写的)
方法一：暴力法
没错，就是直接把这个数组的所有子序列的和都算一遍，跟初始最大值比较，代码如下：
int main()
{
int a[] = {-2,11,-4,13,-5,2,-5,-3,12,-9};
int maxSum = a[0],n = sizeof(a)/sizeof(a[0]);
for(int i = 0;i < n;i++)//子数组长度
{
for(int j = 0;j < n;j++)//子数组开始的位置，数组下标
{
int sum = 0;//记录当前子数组和
for(int k = j;k < n&&k < j + i;k++)//求和
{
sum += a[k];
}
if(sum > maxSum) maxSum = sum;
}
}
cout << "子序列的最大和是："<< maxSum << endl;
return 0;
}
对，就是这么暴力，效率很低，时间复杂度：O(n³)
方法二：递进求和
不断求出以a[i]开头的子序列的和，并在求的过程中记录好最大的子序列的和，函数代码如下：
int maxSubArraySum(int *arr,int n)
{
int i,j,maxSum = 0,sum;
for(i = 0;i < n;i++)//子数组开始位置
{
sum = 0;
for(j = i;j < n;j++)
{
sum += arr[j];
if(sum > maxSum) maxSum = sum;//求和并比较
}
}
return maxSum;
}
相对方法一来说，方法二减少了一次遍历，时间复杂度为：O(n²)
方法三：判断求和
仔细想一下，一个数，加上一个负数会变小，加上零不变，加上正数才会变大，对，就是这么简单的道理，就可以用来优化这个题的算法了。从a[0]开始累加，如果大于初始值，就替换，如果和小于零，直接舍弃，然后是a[1]，函数代码如下：
int maxSubArraySum_2(int *arr,int n)
{
int i,maxSum = arr[0],sum = 0;
for(i = 0;i < n;i++)//子数组开始位置
{
sum += arr[i];
if(sum > maxSum) maxSum = sum;//记录最大累加和
if(sum < 0) sum = 0;//累加和小于零的不要
}
return maxSum;
}
这样的话，只要对数组遍历一次就能解决了，时间复杂度降为O(n)，最简单道理往往有意想不到的效果，哈哈哈哈。
另外，加个