最大连续子序列和 最大连续子序列和 例题 代码 代码
因为最大 连续子序列和只可能是以位置0～n-1中某个位置结尾。当遍历到第i个元素时，判断在它前面的连续子序列和是否大于0，如果大于0，则以位置i结尾的最大连续子序列和为元素i和前门的连续子序列和相加；否则，则以位置i结尾的最大连续子序列和为元素i。
例题
相关题目练习：
hdu 1003：http://acm.hdu.edu.cn/showproblem.php?pid=1003
代码
#include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; int main() { int n,k; int pos1 = 1, pos2 = 1, x = 1; int maxx, now; scanf("%d", &n); for (int j = 1; j <=n; j++) { int temp; scanf("%d", &k); scanf("%d", &temp); pos1 = 1, pos2 = 1, x = 1; maxx = now = temp; for (int i = 2; i <= k; i++) { scanf("%d", &temp); if (now + temp < temp) { now = temp; x = i; } else now += temp; if (now > maxx) { maxx = now; pos1 = x; pos2 = i; } } printf("Case %d: ", j); printf("%d %d %d ", maxx, pos1, pos2); if (j != n)printf(" "); } }
hdu 1231：http://acm.hdu.edu.cn/showproblem.php?pid=1231
代码
#include<iostream> #include<cstdio> #include<string> #include<cstring> using namespace std; int dp[10003]; int main() { int n; int pos1 = 1, pos2 = 1, x = 1; int maxx, now; while (1) { scanf("%d", &n); if (n == 0)break; memset(dp, 0, sizeof(dp)); int temp; scanf("%d", &dp[1]); pos1 = 1, pos2 = 1, x = 1; maxx = now = dp[1]; for (int i = 2; i <= n; i++) { scanf("%d", &dp[i]); } for (int i = 2; i <= n; i++) { if (now + dp[i] < dp[i]) { now = dp[i]; x = i; } else now += dp[i]; if (now > maxx) { maxx = now; pos1 = x; pos2 = i; } } if(maxx<0) printf("%d %d %d ", 0, dp[1], dp[n]); else printf("%d %d %d ", maxx, dp[pos1], dp[pos2]); } }