poj 2593 & poj 2479解题报告

78 阅读 0 评论 52 点赞

我是靠谱客的博主高兴保温杯，最近开发中收集的这篇文章主要介绍poj 2593 & poj 2479解题报告，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

说明：poj 2593与poj 2479基本一样，所以下文以2593为例展开

题目

Max Sequence

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 9370		Accepted: 3825

Description

Give you N integers a1, a2 ... aN (|ai| <=1000, 1 <= i <= N).

You should output S.

Input

The input will consist of several test cases. For each test case, one integer N (2 <= N <= 100000) is given in the first line. Second line contains N integers. The input is terminated by a single line with N = 0.

Output

For each test of the input, print a line containing S.

Sample Input

5
-5 9 -5 11 20
0

Sample Output

Source

POJ Monthly--2005.08.28,Li Haoyuan

解题思路

此题的解题方法属于动态规划的思想。求某个数组序列中两个不重叠的子列，并且这两个子列的和是所有满足条件的子列和中最大的一个。

为了满足不重叠，于是分别从左到右和从右到左扫描数组序列，分别用两个数组left[i]/right[j]数组存储“array[0~i]数组序列中的和最大子序列的和的值”和“array[j~n-1]数组序列中的和最大子序列的值”。于是，两个满足条件的子序列的和，可以通过求最大的 "left[i-1]+right[i]"得到。

另外求“array[0~i]数组序列中的和最大子序列的和的值”的方法，也就是求“某个数组序列和最大子序列”的问题，充分利用动态规划的思想，即可求的。

程序代码

/************************************************************
Problem:2593-Max Sequence
Author:***
Date:2010.5.25
Complexity:O(n)
Problem Type:Dynamic Programming
Memory:1300K
Time:188MS
************************************************************/
#include <cstdio>
#define INT_MIN -1000000000
#define MAX( x, y ) (x>y?x:y)
int array[100000]={INT_MIN};
int left[100000]={INT_MIN};
int right[100000]={INT_MIN};
int resultArray[100]={0};
int N=0;//the number of the elements in the array
int MaxSequence()
{
    /*find the maximum sum of a subsequence from the left of the array*/
    left[0]=array[0];
    for (int i=1; i<N; i++)
    {
        if (left[i-1]>=0) left[i]=left[i-1]+array[i];
        else left[i]=array[i];
    }
    for (int i=1; i<N; i++)
        left[i]=MAX(left[i-1], left[i]);
    /*find the maximum sum of a subsequence from the right side of the array*/
    right[N-1]=array[N-1];
    for (int i=N-2; i>=0; i--)
    {
        if (right[i+1]>0)right[i]=right[i+1]+array[i];
        else right[i]=array[i];
    }
    for (int i=N-2; i>=0; i--)
        right[i]=MAX(right[i+1], right[i]);
    /*find the masimum sum of two non-overlapping subsequences of the array*/
    int ret=INT_MIN;
    for (int i=1; i<N; i++)
    {
        ret=MAX(ret, left[i-1]+right[i]);
    }
    return ret;
}
int main()
{
    int caseNumber=0;
    int value=0;
    scanf("%d", &value);
    while (value)
    {
        N=value;
        for (int i=0; i<N; i++)
        {
            scanf("%d", &value);
            array[i]=value;
        }
        resultArray[caseNumber]=MaxSequence();
        scanf("%d", &value);
        caseNumber++;
    }
    for (int j=0; j<caseNumber; j++)
    {
        printf("%d/n", resultArray[j]);
    }
    return 0;
}