###問題
> 給定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)
