Description
Given a set of n integers: A={a1, a2,..., an}, we define a function d(A) as below: Your task is to calculate d(A).Input
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.Output
Print exactly one line for each test case. The line should contain the integer d(A).Sample Input
1 10 1 -1 2 2 3 -3 4 -4 5 -5Sample Output
13和poj2593几乎一样。https://www.cnblogs.com/Weixu-Liu/p/10512447.htmlC++代码： #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
相关资源：JAVA上百实例源码以及开源项目