Maximum sum
题意：给定一个长度为N的数组，求两个连续的子序列，使得两个连续子序列的和最大。
分析：乍一看，跟最大连续和有点类似，但是，又有区别，因为对于这个题，考虑第i项两个连续子序列的最大和，不能仅仅由前i-1项递推得出，第i项两个连续子序列的最大和，与前i项和i以后的之间是存在关系的，因此这个题目是一个双向dp。
假如给定的序列为a0, a1, a2, a3, a4, …… ,an，那么，对于任意第i项，我以第i个元素为分界点，用一个数组项pMax [i]来保存 区间 [1,i ] 的最大连续子段和【包含第i点】，然后我用nMax[i] 来保存 区间 [i,N] 的最大连续子段和，对于整个区间 [1,N] 来说，两个最大连续子序列的和 Ans = max（pMax[i] + pMaxi+1]）【这时i∈[1,N]即可】，这个过程的复杂度为O（N）。这样我就将这个问题就转化为 求两个区间的最大连续和的问题了【求最大连续和的方法我便不再累赘啦】，，这个过程的复杂度也为O（N），那么这样，整个问题就解决了。
附上一份ac代码【代码很糙，也没去优化了~】：
#include <cmath>#include <cstdio>#include <string>#include <cstring>#include <iomanip>#include <iostream>#include <algorithm>using namespace std;const int maxn = 50000+10;const int INF = 0x7fffffff;int T,N,arr[maxn];int prev[maxn],next[maxn],ans,pMax[maxn],nMax[maxn];//prev[i]保存以第i个元素结尾的连续和，用来求pMax//next[i]保存以第i个元素开头的连续和，用来求nMaxint main(){// freopen("input.in","r",stdin);for(scanf("%d",&T); T–;){scanf("%d",&N);memset(prev,0,sizeof(prev));memset(next,0,sizeof(next));memset(nMax,0,sizeof(nMax));memset(pMax,0,sizeof(pMax));int pre_max,nex_max;for(int i = 1; i <= N; i++){scanf("%d",&arr[i]);if(i == 1) pre_max = prev[i] = arr[1];else{if(prev[i-1] <= 0) prev[i] = arr[i];else prev[i] = prev[i-1]+arr[i];}pre_max = max(prev[i],pre_max);pMax[i] = pre_max;}nMax[N] = nex_max = next[N] = arr[N];for(int i = N-1; i >= 1; i–){if(next[i+1] <= 0)next[i] = arr[i];else next[i] = next[i+1]+arr[i];nex_max = max(nex_max,next[i]);nMax[i] = nex_max;}ans = -INF;for(int i = 1; i < N; i++){ans = max(pMax[i]+nMax[i+1],ans);}printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
而是他们在同伴们都睡着的时候，一步步艰辛地向上攀爬的。
