Maximum sum
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 39089 | Accepted: 12221 |
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.
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 -5
Sample Output
13
Hint
In the sample, we choose {2,2,3,-3,4} and {5}, then we can get the answer.
Huge input,scanf is recommended.
分别求出两端开始的最大子段和，然后枚举左右两段的分界，找出最大值。
//2016.8.21
#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; const int N = ;
const int inf = 0x3f3f3f3f;
int a[N], dpl[N], dpr[N];//dpl[i]表示从左往右到第i位的最大子段和,dpr[i]表示从右往左到第i位的最大子段和 int main()
{
int T, n;
cin>>T;
while(T--)
{
scanf("%d", &n);
for(int i = ; i < n; i++)
{
scanf("%d", &a[i]);
}
memset(dpl, , sizeof(dpl));
memset(dpr, , sizeof(dpr));
//从左往右扫
//*************************************************
dpl[] = a[];
for(int i = ; i < n; i++)
if(dpl[i-]>) dpl[i] = dpl[i-]+a[i];
else dpl[i] = a[i];
for(int i = ; i < n; i++)
if(dpl[i]<dpl[i-])
dpl[i] = dpl[i-];
//从右往左扫
//*************************************************
dpr[n-] = a[n-];
for(int i = n-; i>=; i--)
if(dpr[i+]>) dpr[i] = dpr[i+]+a[i];
else dpr[i] = a[i];
for(int i = n-; i>=; i--)
if(dpr[i]<dpr[i+])
dpr[i] = dpr[i+];
//*************************************************
int ans = -inf;
for(int i = ; i < n-; i++)
{
ans = max(ans, dpl[i]+dpr[i+]);
}
cout<<ans<<endl;
} return ;
}