[poj 2479]Maximum sum

发表于   |  

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 -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.

Source

POJ Contest,Author:Mathematica@ZSU

Solution

呜呜呜。。。。。

  1. 直接求完f[i]（以i结尾的最大），g[i]就交了
  2. 求了累加继续错
  3. 考虑到不能不选，改成 f[i]=MAX(f[i-1]+a[i],a[i])
  4. 还是错
  5. 忘记把ans=-INF
  6. 递推起点应该是f[1]=a[1]而不是f[0]=0，这样负数就搞不出来了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <cstdio>
#include <algorithm>
#define max(a,b) (a)>(b) ? (a):(b)
#define ll long long
#define maxn 500000+100 
using namespace std;

int n,T;
int a[maxn],f[maxn],g[maxn];
int main(){
    freopen(""1.in"",""r"",stdin);
    freopen(""1.out"",""w"",stdout);
    scanf(""%d"",&T);
    while (T--){
        scanf(""%d"",&n);
        for (int i=1;i<=n;i++){
            scanf(""%d"",&a[i]);
        }    
        f[1]=a[1];
        for (int i=2;i<=n;i++){
            // if (f[i-1]+a[i]<0) f[i]=0;
            // else f[i]=f[i-1]+a[i];
            f[i]=max(f[i-1]+a[i],a[i]);
        }
        //for (int i=1;i<=n;i++) f[i]=max(f[i-1],f[i]);
        g[n]=a[n];
        for (int i=n-1;i>=1;i--){
            // if (g[i+1]+a[i]<0) g[i]=0;
            // else g[i]=g[i+1]+a[i];
            g[i]=max(g[i+1]+a[i],a[i]);
        }
        for (int i=n-1;i>=1;i--) g[i]=max(g[i+1],g[i]);
        int ans=-2100000000;
        for (int i=2;i<=n;i++){
            if (g[i]+f[i-1]>ans){
                ans=g[i]+f[i-1];
            }
        }
        printf(""%d\n"",ans);
    }
}