poj2479与poj2593,同一道DP题

9月 15

这两道题的题目的题目大意如上，对于输入的n个数，求出最大的S,这是一个简单的DP题，开两个数组，DP[i][0],DP[i][1];,其中DP[i][0]表示的是从0～i中连续子串的最大和,DP[i][1]表示i～n-1中连续子串的最大和,则题目就变成求max{DP[i][0]+DP[i+1][1]}

参考代码：
poj2479

poj2479 Maximum sumview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[50005];
int dp[50005][2];
int i ;
int main()
{
    int t ;
    scanf("%d",&t);
    while ( t -- )
    {
        int n ;
        int sum=0;
        scanf("%d",&n);
        for ( i = 0 ; i < n ; i ++ )
        {
            scanf ("%d", &a[i]) ;
            if (  i )
            {
                sum = max(sum+a[i],a[i]);
                dp[i][0]=max(sum,dp[i-1][0]);
            }
            else
                dp[i][0]=sum=a[i];
        }
        for ( i = n -1 ; i>=0 ; i -- )
        {
            if ( i != ( n - 1 ) )
            {
                sum = max(sum + a[i] , a[i]);
                dp[i][1]=max(sum,dp[i+1][1]);
            }
            else
                dp[i][1]=sum=a[i];
        }
        sum = -(1<<30) ;
        for ( i = 0 ; i < n - 1 ; i ++ )
            sum = max ( sum , dp[i][0]+dp[i+1][1] );
        printf("%d\n",sum);
    }
    return 0;
}

poj2593

poj2593 Max Sequenceview raw

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int a[100005];
int dp[100005][2];
int i ;
int main()
{
    int n ;
    while ( scanf("%d",&n) , n )
    {

        int sum=0;
        for ( i = 0 ; i < n ; i ++ )
        {
            scanf ("%d", &a[i]) ;
            if (  i )
            {
                sum = max(sum+a[i],a[i]);
                dp[i][0]=max(sum,dp[i-1][0]);
            }
            else
                dp[i][0]=sum=a[i];
        }
        for ( i = n -1 ; i>=0 ; i -- )
        {
            if ( i != ( n - 1 ) )
            {
                sum = max(sum + a[i] , a[i]);
                dp[i][1]=max(sum,dp[i+1][1]);
            }
            else
                dp[i][1]=sum=a[i];
        }
        sum = -(1<<30) ;
        for ( i = 0 ; i < n - 1 ; i ++ )
            sum = max ( sum , dp[i][0]+dp[i+1][1] );
        printf("%d\n",sum);
    }
    return 0;
}