POJ 2479 Maximun sum解题报告

时间：2010-05-31 来源：华南理工大学

一、问题描述

http://acm.pku.edu.cn/JudgeOnline/problem?id=2479

二、解题思路

联想到最大子段和的求法。s[i]表示以i为起点的最大的子段和，t[i]表示以i结尾的最大的子段和。M1[i]表示1-i中的最大子段和，M2[i]表示i-n中的最大子段和。可知结果为res=max(M1[i]+M2[i+1])(1<=i<n);时间复杂度为O(n)。

三、代码

#include<iostream>
using namespace std;
int a[50005];
int s[50005];
int t[50005];
int T,n;
int main()
{
    scanf("%d",&T);
    int i,j;
    for(i=0;i<T;++i)
    {
        char ch[3];
        gets(ch);
        scanf("%d",&n);
        for(j=1;j<=n;++j)
            scanf("%d",&a[j]);
        t[0]=0;
        for(j=1;j<=n;++j)
        {
            if(t[j-1]<0)
                t[j]=a[j];
            else
                t[j]=t[j-1]+a[j];
        }
        int iMax=t[1];
        for(j=1;j<=n;++j)
        {
            if(iMax > t[j])
                t[j]=iMax;
            else
                iMax = t[j];
        }

        s[n]=a[n];
        for(j=n-1;j>0;--j)
        {
            if(s[j+1] > 0)
                s[j]=a[j]+s[j+1];
            else
                s[j]=a[j];
        }
        iMax=s[n];
        for(j=n-1;j>0;--j)
        {
            if(iMax > s[j])
                s[j]=iMax;
            else
                iMax=s[j];
        }
        iMax=-999999999;
        int temp;

        for(j=2;j<=n;++j)
        {
            temp=t[j-1]+s[j];
            if(temp > iMax)
                iMax=temp;
        }
        printf("%d\n",iMax);
    }
    return 0;
}