POJ 2479 Maximum sum

迈不过友情╰ 2022-05-28 05:36 105阅读 0赞

Maximum sum  
Time Limit: 1000MS Memory Limit: 65536K  
Total Submissions: 42643 Accepted: 13273  
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

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.

## 题目大意： ##

这个题目意思非常容易理解，就是让我们求一个数串的两个不想交的连续序列的和最大

## 题目解析: ##

这个题目是一个简单的dp问题，首先我的做法是先求出以i为结尾的连续序列喝的最大值，这个很好理解，也很容易推出状态转移方程，dp\[i\[表示以i为结尾的连续序列和的最大值，状态转移方程为dp\[i\] = max(a\[i\]+dp\[i-1\],a\[i\]);在求出以i为开头的连续序列和的最大值，这个只需要倒过来求一下即可，同样，dp\[i\]表示以i为开头的连续序列和的最大值，很容易得出状态转移方程为dp\[i\] = max(dp\[i+1\]+a\[i\],a\[i\]),然后我们只需要把以i为结尾的序列的最大值放在ans1\[i\]中，把以i为开头的序列的最大值放在ans2\[i\]中，然后直接通过一个循环遍历一下，即可求出最大值，注意：用scanf输出，cin输入可能会超时。

## 代码： ##

#include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    const int maxn = 1e6;
    int a[maxn];
    int dp1[maxn],dp2[maxn];
    int ans1[maxn],ans2[maxn];
    int main()
    {
        //freopen("in.txt","r",stdin);
        int T,n;
        scanf("%d",&T);
        while(T--)
        {
            int ans = -1000;
            memset(a,0,sizeof(a));
            memset(dp1,0,sizeof(dp1));
            memset(dp2,0,sizeof(dp2));
            memset(ans1,0,sizeof(ans1));
            memset(ans2,0,sizeof(ans2));
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                scanf("%d",&a[i]);
            dp1[0] = a[0];
            ans1[0] = a[0];
            for(int i=1; i<n; i++)
            {
                dp1[i] = max(a[i],dp1[i-1]+a[i]);
                if(dp1[i]>ans1[i-1])
                    ans1[i] = dp1[i];
                else
                    ans1[i] = ans1[i-1];
            }
            dp2[n-1] = a[n-1];
            ans2[n-1] = a[n-1];
            for(int i=n-2; i>=0; i--)
            {
                dp2[i] = max(a[i],dp2[i+1]+a[i]);
                if(dp2[i]>ans2[i+1])
                    ans2[i] = dp2[i];
                else
                    ans2[i] = ans2[i+1];
            }
            for(int i=0;i<n-1;i++)
                ans = max(ans,ans1[i]+ans2[i+1]);
            printf("%d\n",ans);
        }
        return 0;
    }