（线性dp，最大连续和）Max Sequence

Max Sequence Time Limit: 3000MS Memory Limit: 65536KTotal Submissions: 18511 Accepted: 7743

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).  You should output S. 

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5 -5 9 -5 11 20 0

Sample Output

40最大连续和问题的升级版，先从左边遍历一次，从右边遍历一次，分成两部分，然后相加，最后取最大值。 最大连续和的状态转换式为：dp[i] = max(dp[i-1]+a[i],a[i])可以打表，注意两次遍历时的初始化情况，还有得用m1和m2数组保存前i个数的最大连续和和后j个数的最大连续和。这样接下来就可以用m1[i] + m2[i+1]的最大值作为答案。C++代码： #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn = 100005; int a[maxn],dpl[maxn],dpr[maxn],m1[maxn],m2[maxn]; int Inf = -0x3f3f3f3f; int main(){ int n; while(~scanf("%d",&n)){ if(n==0) break; for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); } memset(dpl,0,sizeof(dpl)); memset(dpr,0,sizeof(dpr)); m1[0] = m2[n+1] = Inf; for(int i = 1; i <= n; i++){ dpl[i] = max(dpl[i-1] + a[i],a[i]); if(m1[i-1] < dpl[i]) m1[i] = dpl[i]; else m1[i] = m1[i-1]; } for(int i = n; i >= 1; i--){ dpr[i] = max(dpr[i+1] + a[i],a[i]); if(m2[i+1] < dpr[i]) m2[i] = dpr[i]; else m2[i] = m2[i+1]; } int maxsum = Inf; int tmp[maxn]; for(int i = 1; i <= n-1; i++){ tmp[i] = m1[i] + m2[i+1]; if(maxsum < tmp[i]) maxsum = tmp[i]; } printf("%d\n",maxsum); } return 0; }

 

转载于:https://www.cnblogs.com/Weixu-Liu/p/10512447.html

相关资源：用DP算法的PKU2593Max Sequence的源代码