定义两个数组l[],r[]。l[k]表示下标[1...k]范围内的最大连续和，r[k]表示下标[k...n]范围内的最大连续和，O(n)遍历k取最大即可。

Note. l[k]不表示k必须入选，r[k]同理。假定ll[k]表示k必须入选，用最大值过一遍ll[k]就得到l[k]了，r[k]同理。总时间还是O(n)。


#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int a[50002];
long long l[50002];
long long r[50002];
const long long INF = 1 << 30;

int main()
{
    int T;
    scanf("%d",&T);
    for(int t = 0;t < T;t++)
    {
        int n;
        scanf("%d",&n);
        for (int i = 0;i < n;i++)
        {
            scanf("%d",&a[i]);
        }

        l[0] = a[0];
        long long sum = l[0];
        for (int i = 1;i < n;i++)
        {
            if (sum < 0)
            {
                l[i] = a[i];
                sum = l[i];
            }
            else
            {
                l[i] = sum + a[i];
                sum = l[i];
            }
        }
        sum = -INF;
        for (int i = 0;i < n;i++)
        {
            sum = max(sum,l[i]);
            l[i] = sum;
        }

        r[n-1] = a[n-1];
        sum = r[n-1];
        for (int i = n-2;i >= 0;i--)
        {
            if (sum < 0)
            {
                r[i] = a[i];
                sum = r[i];
            }
            else
            {
                r[i] = sum + a[i];
                sum = r[i];
            }
        }
        sum = -INF;
        for (int i = n-1;i >= 0;i--)
        {
            sum = max(sum,r[i]);
            r[i] = sum;
        }
        
        sum = -INF;
        for (int i = 0;i < n-1;i++)
        {
            sum = max(sum,l[i]+r[i+1]);
        }

        printf("%lld\n",sum);
    }
    return 0;
}

• Re:AC解，本人水，仅供参考 (29) xiakk0 2010-08-10 11:26:33
  • Re:AC解，本人水，仅供参考 (43) KevinQian 2012-05-04 19:43:44