程序填空题：最大子段和问题（分治法）
最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。
```c++
#include
#include
#include
using namespace std;
#define N 10001
long maxsubsum(int *a,int left,int right)
{
long sum=0;
if(left==right)
sum=@@[a[left]>0?a[left]:0](2);
else{
int center=(left+right)/2;
long leftsum=@@[maxsubsum(a,left,center)](2);
long rightsum=@@[maxsubsum(a,center+1,right)](2);
long s1=0;
long lefts=0;
for(int i=center;i>=left;i--){
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
long s2=0;
long rights=0;
for(int i=center+1;i<=right;i++){
rights+=a[i];
if(rights>s2)
s2=rights;
}
@@[sum=s1+s2](2);
if(sum sum=leftsum;
if(sum sum=rightsum;
}
return sum;
}
int main()
{
int n,i;
int a[N];
long sum=0;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
sum=@@[maxsubsum(a,1,n)](2);
cout< return 0;
}
```
### 输入格式:
第一行输入整数个数n（1≤n≤1000），再依次输入n个整数。
### 输出格式:
输出最大子段和。
### 输入样例1:
```in
5
-2 11 -4 13 -5 -2
```
### 输出样例1:
```out
20
```
答案：
第1空：a[left]>0?a[left]:0
第2空：maxsubsum(a,left,center)
第3空：maxsubsum(a,center+1,right)
第4空：sum=s1+s2
第5空：maxsubsum(a,1,n)
```c++
#include
#include
#include
using namespace std;
#define N 10001
long maxsubsum(int *a,int left,int right)
{
long sum=0;
if(left==right)
sum=@@[a[left]>0?a[left]:0](2);
else{
int center=(left+right)/2;
long leftsum=@@[maxsubsum(a,left,center)](2);
long rightsum=@@[maxsubsum(a,center+1,right)](2);
long s1=0;
long lefts=0;
for(int i=center;i>=left;i--){
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
long s2=0;
long rights=0;
for(int i=center+1;i<=right;i++){
rights+=a[i];
if(rights>s2)
s2=rights;
}
@@[sum=s1+s2](2);
if(sum
if(sum
}
return sum;
}
int main()
{
int n,i;
int a[N];
long sum=0;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
sum=@@[maxsubsum(a,1,n)](2);
cout<
}
```
### 输入格式:
第一行输入整数个数n（1≤n≤1000），再依次输入n个整数。
### 输出格式:
输出最大子段和。
### 输入样例1:
```in
5
-2 11 -4 13 -5 -2
```
### 输出样例1:
```out
20
```
答案：
第1空：a[left]>0?a[left]:0
第2空：maxsubsum(a,left,center)
第3空：maxsubsum(a,center+1,right)
第4空：sum=s1+s2
第5空：maxsubsum(a,1,n)
