程序填空题：最大子段和问题（动态规划法）

最大子段和问题。给定由n个整数组成的序列，求序列中子段的最大和，若所有整数均为负整数时定义最大子段和为0。

### 输入格式:

第一行输入整数个数n（1≤n≤10000），再依次输入n个整数。

### 输出格式:

输出第一行为最大子段和，第二行为子段第一个数和最后一个数在整个序列中的位序(下标)。

### 输入样例1:

```in
5
-2 11 -4 13 -5 -2
```

### 输出样例1:

```out
20
2 4
```

```c++
#include 
#include
#include 
#define max(x,y) ((x)>(y)?(x):(y))
#define MAXN 20
using namespace std;
#define N 10001
//问题表示
int n;
int a[N];
//求解结果表示
int dp[MAXN];
void maxSubSum()				//求dp数组
{
	dp[0]=0;
	for (int j=1;j<=n;j++)
		dp[j]=;
}
void dispmaxSum()					//输出结果
{
	int maxj=1;
	for (int j=2;j<=n;j++)		
		if () maxj=j;

	int k;	
	for (k=maxj;k>=1;k--)		
		;
	printf("%d\n",dp[maxj]);
	printf("%d %d",k+1,maxj);
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];	
	maxSubSum();
	dispmaxSum();
	return 0;
}
```






答案：
第1空：max(dp[j-1]+a[j],a[j])    

第2空：dp[j]>dp[maxj]    

第3空：if (dp[k]<=0) break