首页 > 代码库 > POJ_2593_DP

POJ_2593_DP

http://poj.org/problem?id=2593

 

和2479一样。

 

#include<iostream>#include<cstdio>#define MIN -0x3f3f3f3f;using namespace std;int a[100005],lmax[100005],rmax[100005],n;int main(){    while(scanf("%d",&n) && n)    {        lmax[0] = MIN;        rmax[n+1] = MIN;        for(int i = 1;i <= n;i++)    scanf("%d",&a[i]);        int sum = 0;        for(int i = 1;i <= n;i++)        {            sum += a[i];            if(lmax[i-1] < sum)    lmax[i] = sum;            else    lmax[i] = lmax[i-1];            if(sum < 0)    sum = 0;        }        sum = 0;        for(int i = n;i >= 1;i--)        {            sum += a[i];            if(rmax[i+1] < sum)    rmax[i] = sum;            else    rmax[i] = rmax[i+1];            if(sum < 0)    sum = 0;        }        int maxx = MIN;        for(int i = 1;i < n;i++)    maxx = max(maxx,lmax[i]+rmax[i+1]);        printf("%d\n",maxx);    }    return 0;    }

 

POJ_2593_DP