POJ 2593&&2479：Max Sequence - c++编程基础

TOP

POJ 2593&&2479：Max Sequence

2015-11-21 00:58:08 来源: 作者: 【大中小】浏览:2次

Max Sequence

Time Limit: 3000MS	?	Memory Limit: 65536K
Total Submissions: 16329	?	Accepted: 6848

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 200

Sample Output

题意是给出一个序列，求这个序列中两个子序列的和的最大值。两三年前切了POJ2479，但当时还很不理解dp (当然现在对dp的理解程度也就能切切dp水题。。。)。所以做这道题的时候无限感慨。其实求一个序列的和的最大值很简单，即dp[i]=max(dp[i-1]+value[i], value[i]) 现在它要求两个序列的和的最大值。所以想到从左边来一次，从右边来一次。 left[i]表示从第1个数字到当前第i个数字为止，左边的最大序列和。 right[i]表示从第Test个数字(从右向左)到第i个数字为止，右边的最大序列和。
代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int left_v[100005]; int right_v[100005]; int value[100005]; int main() { int Test; while(cin>>Test) { if(!Test) break; left_v[0]=0; right_v[0]=0; left_v[Test+1]=0; right_v[Test+1]=0; int i,max_v=-100000000; for(i=1;i<=Test;i++) { cin>>value[i]; } left_v[1]=value[1]; right_v[Test]=value[Test]; for(i=2;i<=Test;i++) { left_v[i]=max(left_v[i-1]+value[i],value[i]); } for(i=Test-1;i>=1;i--) { right_v[i]=max(right_v[i+1]+value[i],value[i]); } for(i=2;i<=Test;i++) { left_v[i]=max(left_v[i-1],left_v[i]); } for(i=Test-1;i>=1;i--) { right_v[i]=max(right_v[i+1],right_v[i]); } for(i=1;i
     
      max_v) max_v=left_v[i]+right_v[i+1]; } cout<
      
        自己把这道题A掉，相当开心。2015/7/5。


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu(3016) Man Down(线段树查询更..	下一篇：HDU 1043 Eight (BFS·八数码..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: