最大子序列和——HDU-1003 Max Sum
题目大意：给定序列个数n及n个数，求该序列的最大连续子序列的和，要求输出最大连续子序列的和以及子序列的首位位置
解题思路：经典DP，可以定义dp[i]表示以a[i]为结尾的子序列的和的最大值，因而最大连续子序列及为dp数组中的最大值。
状态转移方程：dp[1] = a[1]; //以a[1]为结尾的子序列只有a[1]；
i >= 2时， dp[i] = max( dp[i-1]+a[i], a[i] );
dp[i-1]+a[i] > a[i]时，即dp[i-1](以a[i-1]为结尾的子序列的和的最大值)的值为正，那么dp[i-1]则对dp[i]有贡献，
dp[i-1]+a[i] < a[i]时，即dp[i-1] < 0，那么抛弃它，dp[i] = a[i]
例子：序列 6 -7 5 2 -3， 则dp[i]分别为 6 -1 5 7 4，注意dp[2]直接用a[2]表示，因为dp[1] = -1 < 0; 最后最大子序列和即为dp数组中的最大值 5;
至于位置的记录，则再每次获取到最大值时更新即可。另外此题是从前往后更新，可直接使用a[i]数组而省下一个dp数组。
//最大子序列和 #include <iostream> #include <cstdio> #include <math.h> #include <string.h> #include <string> using namespace std; int dp[100010]; int t,m,l,r,start,maxx; int main() { scanf("%d",&t); for(int i=1;i<=t;i++) { scanf("%d",&m); for(int j=1;j<=m;j++) { scanf("%d",&dp[j]); } l = r = start = 1; maxx = dp[1]; for(int j=2;j<=m;j++) { if(dp[j-1] >= 0) dp[j] = dp[j-1] +dp[j]; else start = j; if(dp[j] > maxx){ maxx = dp[j]; l = start; r = j; } } cout <<"Case "<<i<<":\n"<<maxx<<" "<<l<<" "<<r<<endl; if(i != t) cout<<endl; } return 0; }
第二种解法 ，直接在输入的时候判断是否形成最大子序列，如果数列小于零，则一直重排，不过maxx最好定义的足够小，否则会因为全部是负数这个点wa掉
#include <iostream> #include <math.h> #include <cstdio> using namespace std; int main() { int t; scanf("%d",&t); for(int i=1;i<=t;i++) { int m,k; int maxx = -10,sum = 0,l = 0,r = 0,cnt = 0,temp;// l 不是左下标 而是maxx序列的个数 scanf("%d",&m); int m2 = m; while(m--) { scanf("%d",&k); sum += k; cnt++; if(sum > maxx){ l = cnt; maxx = sum; r = m2 - m; } if(sum < 0){ sum = 0; cnt = 0; } } cout <<"Case "<<i<<":\n"<<maxx<<" "<<r-l+1<<" "<<r<<endl; if(i != t) cout<<endl; } return 0; }
网易游戏公司福利 279人发布
