DP专题3 POJ 2593 Max Sequence
传送门：http://poj.org/problem?id=2593
Max Sequence
#include <stdio.h>#include <stdlib.h>int input[100010];int s[100010];int temp[100010];int dp(int i , int j){ int m , flag ; if(i == j) return input[i]; //m = i + 1; temp[i] = input[i]; for(m = i+1 ; m <= j ; m ++) { if(temp[m-1]>0) temp[m] = temp[m-1] + input[m]; else temp[m] = input[m]; } flag = temp[i]; for(m = i + 1 ; m <= j ; m ++) if(temp[m]>flag) flag = temp[m]; return flag;}int main(){ int n , i; int sl,sr,flag; while(scanf("%d",&n),n) { for(i = 1 ; i <= n ; i ++) scanf("%d",&input[i]); memset(temp,0,sizeof(temp)); for(i = 1 ; i <= n - 1 ; i ++) { sl = dp(1,i); sr = dp(i+1,n); s[i] = sl + sr ; } flag = s[1]; for(i = 1 ; i <= n - 1 ; i++) if(s[i]>flag) flag = s[i]; printf("%d\n",flag); } return 0;}
回过头来看，确实，o(n^2)的复杂度，而数据最多可达100000，并且POJ经常越界测试，所以超时就再所难免了。
再看看有没有其他的算法呢，上面我们是从1→i和i+1→n分别测试，1→i和i+1→n的区别就在于前者的头不动，后者的尾巴不动，如果我们把后者倒过来算，这样两者就一样了，时间会不会缩减呢。这里我们干脆把整个数组按照DP2专题中的方法正着来一遍，反着来一遍，然后取left[i]+right[i+1]即可。
代码如下：
/*Memory: 1560 KB Time: 204 MS Language: GCC Result: Accepted This source is shared by hust_lcl*/#include <stdio.h>#define SIZE 100010int input[SIZE];int left[SIZE];int right[SIZE];int main(){ int n , i , j , max , flag , t; while(scanf("%d",&n),n) { for(i = 1 ; i <= n ; i++) scanf("%d",&input[i]); left[1] = input[1]; for(i = 2 ; i <= n ; i ++) { if(left[i-1]>0) left[i] = input[i] + left[i-1]; else left[i] = input[i]; } right[n] = input[n]; t = 0; for(i = n-1 ; i >=1 ; i --) { if(right[i+1]>0) { if(input[i]>0) right[i] = right[i+1] + input[i]; else right[i] = right[i+1]; } else { if(input[i]<0) right[i] = input[i]>right[i+1]?input[i]:right[i+1]; else right[i] = input[i]; } } max = left[1] + right[2]; for(i = 2 ; i <=n - 1 ; i ++) { if(left[i]+right[i+1] > max) max = left[i] + right[i+1]; } printf("%d\n",max); }}