| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 44459 | Accepted: 13794 |
Description
Your task is to calculate d(A).
Input
Output
Sample Input
1 10 1 -1 2 2 3 -3 4 -4 5 -5
Sample Output
13
和poj2593几乎一样。
https://www.cnblogs.com/Weixu-Liu/p/10511854.html
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 T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); 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/10511895.html