HDU 1003 Max Sum（最大连续子列和）

本文主要是介绍HDU 1003 Max Sum（最大连续子列和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1003

DP经典题目，求最大连续子列和，注意还要输出子列的下标。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int dp[100100];
int main() {int t;while(~scanf("%d", &t)) {int n, s, e, kase = 0;int i, j, tmp, maxn, ms, me;while(t--)  {memset(dp, 0, sizeof(dp));scanf("%d", &n);s = 0, e = 0;for(i = 0; i < n; i++) {scanf("%d", &tmp);if(i == 0) dp[i] = tmp, maxn = tmp, ms = 0, me = 0;else {if(dp[i - 1] < 0) {dp[i] = tmp;s = e = i;	}else {dp[i] = dp[i - 1] + tmp;e = i;}}if(dp[i] > maxn) {maxn = dp[i];ms = s, me = e;}}printf("Case %d:\n", ++kase);printf("%d %d %d\n", maxn, ms + 1, me + 1);if(t != 0) putchar('\n');}} return 0;
}

这篇关于HDU 1003 Max Sum（最大连续子列和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---