程序填空题:最大子段和问题(动态规划法)
最大子段和问题。给定由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
### 输入格式:
第一行输入整数个数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