首页 > 代码库 > hdu1003 最大连续子列和（动态规划★★★☆☆）
hdu1003 最大连续子列和（动态规划★★★☆☆）
解题思路：
利用动态规划方法求解最大子列和，对应输入数据a[i]，会有数据dp[i]。数组dp中的每个元素dp[i]，表示以a[i]结尾的最大连续子列和。遍历dp数组，可以找出子列和最大值。
if (dp[i-1] >=0){
dp[i] = dp[i-1] + a[i];
}
else{
dp[i] = a[i]
}
#include <iostream>#include <stdio.h>#include <stdlib.h>using namespace std;int r[100001];int main(){ //freopen("in.txt","r",stdin); int cs; r[0] = -1000000; scanf("%d",&cs); int n; for(int t=1;t<=cs;t++){ scanf("%d",&n); int s=0,e=0,m=-1000000; int a,b,tmp; for(int i=1;i<=n;i++){ scanf("%d",&r[i]); if(r[i-1]>=0){ r[i]+=r[i-1]; b=i; tmp = r[i]; } else{ a = b = i; tmp = r[i]; } if(tmp>m){ m = tmp; s = a; e = b; } } if(t!=1){ printf("\n"); } printf("Case %d:\n%d %d %d\n",t,m,s,e); } //system("pause"); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。