首页 > 代码库 > HDU1003 Max Sum（最大连续子序列和）
HDU1003 Max Sum（最大连续子序列和）
题目：http://acm.hdu.edu.cn/showproblem.php?pid=1003
简单dp，状态转移方程：sum[i] = max{sum[i-1]+a[i],a[i]}. (sum[i]记录以a[i]为子序列末端的最大连续和.)
对于a[i]这个数字，我们考虑是否将它选入之前连续的序列。
如果选，状态变为sum[i-1]+a[i] ; 如果不选，则从此开始一个新的序列，故和为a[i]。
1 #include<cstdio> 2 int main() 3 { 4 int T, n; 5 scanf("%d", &T); 6 for (int cas = 1; cas <= T; cas++){ 7 scanf("%d", &n); 8 int a, sum = 0, max = -9999, st, ed, x = 1, y = 1; 9 for (int i = 1; i <= n; i++){10 scanf("%d", &a);11 if (sum + a < a)//判断前面的连续序列是否和为负，是就重新开始一个序列12 sum = a, x = y = i;13 else14 sum += a, y = i; 15 if (sum > max)16 max = sum, st = x, ed = y;17 }18 printf("Case %d:\n%d %d %d\n", cas, max, st, ed);19 if (cas != T) puts("");20 }21 return 0;22 }
HDU1003 Max Sum（最大连续子序列和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。