-->
当前位置:首页 > 题库 > 正文内容

程序填空题:最大子段和问题(动态规划法)

Luz4年前 (2021-05-10)题库621
最大子段和问题。给定由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

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。