###问题
> 给定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。
###思路
从第一个元素开始,计算1-2的和、1-3的和、直到1-n的和,sum来记录最大的和,在循环过程中如果有和比sum大,把当前最大和替换掉,记录besti和bestj;然后计算2-3的和、2-4的和、直到2-n的和。需要2次for循环,时间复杂度O(n^2).
###代码
~~~
#include <iostream>
using namespace std;
//求a中的最大子段和
int maxSum(int a[],int n){
int i,j,sum=0,besti,bestj;
for(i=0;i<4;i++){
int newsum=0;
for ( j= i; j <n; ++j)
{
newsum+=a[j];
if(newsum>sum){
sum=newsum;
besti=i;
bestj=j;
}
}
}
cout<<"开始位置:"<<a[besti]<<endl;
cout<<"开始位置:"<<a[bestj]<<endl;
return 0;
}
int main(){
int a[6]={-2,11,-4,13,-5,-2};
maxSum(a,6);
int b[10]={1,-5,6,-2,11,-7,23,-13,15,-3};
maxSum(b,10);
}
~~~
###输出
~~~
开始位置:11
开始位置:13
开始位置:6
开始位置:15
~~~
###时间复杂度
O(n^2)