6
3 3 -3 4 -2 1
看看这组数据，正确结果是10
可有些标程中是11
而且我用结果是11的标程提交是正确的
我说的就是这个标程：

POJ 2593（动态规划）
题目来源 ：PKU 2593

解法类型 ：动态规划应用

作    者 ：刘亚宁
http://acm.pku.edu.cn/JudgeOnline/problem?id=2593

题目大意：
        抽取一个整数序列的两个子序列，求所有抽取方法中得到两个序列和的最大值。

题目思路：
        用两个数组数组记录从前和从后子序列加和的最大值，每个元素的值为从前（后）加和至该位置得到的最大值。
        遍历数组每个位置，找出所有位置为分界点的最大值即为结果。
        其中得到子序列最大和过程比较特殊，详见代码。

提交情况：
        Run time error（以后简称rte）一次：数组不够大，省题没注意数据范围。
        Time Limit Exceeded（以后简称tle）一次：没有应用前和后的数组进行数据的存储。

注意：
        两个子序列和的最大值 不是最大子序列和 与 第二大不想交子序列和 的sum（错因：例如数据3 3 -3 4 -2 1）

源程序：  
代码:
#include <iostream>
#define MIN -2000000000
using namespace std;

long a[110000],front[110000],back[110000];

int main()
{
        long num,i,r,k;
        while(cin>>num,num)
        {
                for(i=1;i<=num;i++) cin>>a[i];
                front[0]=MIN;//特殊处理边界情况
                back[num+1]=MIN;
                for(i=1;i<=num;i++)
                {
                        k=(front[i-1]+a[i])>a[i]?(front[i-1]+a[i]):a[i];
                        front[i]=front[i-1]>k?front[i-1]:k;//从前向后，找到加上a对应位置的值、不加该值、和只有该值（可能是一序列的开头）的最大者，记录于front数组
                }
                for(i=num;i>=1;i--)
                {
                        k=(back[i+1]+a[i])>a[i]?(back[i+1]+a[i]):a[i];
                        back[i]=back[i+1]>k?back[i+1]:k;
                }//从后向前，进行类似的活动
                r=MIN;
                for(i=1;i<num;i++)
                        if(front[i]+back[i+1]>r) r=front[i]+back[i+1];//从 所有前后两个序列的分界位置 所对应的和中 找到最大的 即为结果
                cout<<r<<endl;
        }
        return 0;
}

• Re:谁说这个程序是标程？！！！ (1757) MasterLuo 2008-08-21 00:37:09
  • Re:谁说这个程序是标程？！！！ (52) simple85 2008-08-21 00:46:29
• Re:貌似数据有问题 (1757) z123456789 2009-08-12 13:19:47
• Re:貌似数据有问题 (1757) s2009zy 2010-07-24 17:30:34