#include <iostream>
#include <cstdio>

using namespace std;

//#define DBG

int array[50000];
int sumPre[50000];
int sumSuc[50000];
int maxPre[50000];
int maxSuc[50000];

inline int cal(int *const array, int len)
{
    sumPre[0] = array[0];
    sumSuc[len - 1] = array[len - 1];
    for (int i = 1; i < len; ++i)
    {
        if (sumPre[i - 1] < 0)
        {
            sumPre[i] = array[i];
        }
        else
        {
            sumPre[i] = array[i] + sumPre[i - 1];
        }
    }
    for (int i = len - 2; i >= 0; --i)
    {
        if (sumSuc[i + 1] < 0)
        {
            sumSuc[i] = array[i];
        }
        else
        {
            sumSuc[i] = array[i] + sumSuc[i + 1];
        }
    }

#ifdef DBG
    for (int i = 0; i < len; ++i)
    {
        cout << sumPre[i] << " " ;
    }
    cout << endl;
    for (int i = 0; i < len; ++i)
    {
        cout << sumSuc[i]  << " ";
    }
    cout << endl;
#endif

    maxPre[0] = sumPre[0];
    maxSuc[len - 1] = sumSuc[len - 1];
    int tmpMax;
    tmpMax = sumPre[0];
    for (int i = 1; i < len; ++i)
    {
        if (sumPre[i] > tmpMax)
        {
            tmpMax = sumPre[i];
        } 
        maxPre[i] = tmpMax;
    }
    tmpMax = sumSuc[len - 1];
    for (int i = len - 2; i >= 0; --i)
    {
        if (sumSuc[i] > tmpMax)
        {
            tmpMax = sumSuc[i];
        } 
        maxSuc[i] = tmpMax;
    }

#ifdef DBG
    for (int i = 0; i < len; ++i)
    {
        cout << maxPre[i] << " " ;
    }
    cout << endl;
    for (int i = 0; i < len; ++i)
    {
        cout << maxSuc[i]  << " ";
    }
    cout << endl;
#endif

    tmpMax = maxPre[0] + maxSuc[1]; 
    for (int i = 1; i < len - 1; ++i)
    {
        if (maxPre[i] + maxSuc[i + 1] > tmpMax)
        {
            tmpMax = maxPre[i] + maxSuc[i + 1];
        }
    }

    return tmpMax;
}

#if 1
int main(void)
{
    int count;
    int len;
    cin >> count;
    for (int i = 0; i < count; ++i)
    {
        cin >> len;
        for (int j = 0; j < len; ++j)
        {
            scanf("%d", &array[j]);
        }
        cout << cal(array, len) << endl;
    }
}
#endif

• Re:虽然没有全懂，但还是贴出自己写的ACed代码，仅供参考。 (53) clvcsl 2010-05-26 22:20:36