题目链接
描述Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below:
t1 t2 d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n } i=s1 j=s2 Your task is to calculate d(A).输入The input consists of T(<=30) test cases. The number of test cases (T) is given in the first line of the input. Each test case contains two lines. The first line is an integer n(2<=n<=50000). The second line contains n integers: a1, a2, ..., an. (|ai| <= 10000).There is an empty line after each case.输出Print exactly one line for each test case. The line should contain the integer d(A).样例输入 1101 -1 2 2 3 -3 4 -4 5 -5
样例输出
13
提示In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.这道题目的基础是最大子段和。之前学习过有关的知识，自以为可以很轻松的解决这个问题，直到亲手做了一遍才发现不是那么回事。这道题目在最大子段和的基础上强化了，要求两个不想交的子段的和的最大值。这个问题与另一道问题就很类似
核心的思路就是先求出从前到后以i为结尾的最大子段和，和到i位置的子段和的最大值。然后从后往前进行相同的过程。最后就是求解和的最大值。
代码
#include#include #include #include #include #include #include #define DEBUG(x) cout<<#x<<" = "< < num[i]?sumf[i-1]+num[i]:num[i]; dpf[i]=max(sumf[i],dpf[i-1]); } sumr[N]=num[N]; dpr[N]=sumr[N]; for(int i=N-1;i>=1 ;i-- ){ sumr[i]=sumr[i+1]+num[i]>num[i]?sumr[i+1]+num[i]:num[i]; dpr[i]=max(sumr[i],dpr[i+1]); } int ans=-0x3f3f3f3f; for(int i=1;i<=N-1 ;i++ ){ ans=max(ans,dpf[i]+dpr[i+1]); } printf("%d\n",ans); }}