NEUOJ 1302: 最大子序列(双向dp) - c++编程基础

第一次写dp，有点小激动哈哈，纪念下

1302: 最大子序列

时间限制: 1 Sec 内存限制: 128 MB
提交: 174 解决: 41
[提交][状态][讨论版]

题目描述

给定一个N个整数组成的序列，整数有正有负，找出两段不重叠的连续子序列，使得它们中整数的和最大。两段子序列都可以为空。

输入

多组输入，每组第一行为N，表示序列的长度；第二行为N个整数(-1000<=n<=1000)，表示输入序列。 0

输出

对于每组输入，输出一行，仅一个整数，表示最大的和。

样例输入

9
185 -580 -889 701 964 -878 353 -761 608

样例输出

提示

样例输入序列的一种选择为：(701 964)和(608)

来源

#include 
   
    
#include 
    
      #include 
     
       using namespace std; #define Max 1000002 int num[Max]; int dp1[Max],dp2[Max]; int main() { int n; freopen("input.txt","r",stdin); while( scanf("%d",&n)!=EOF) { memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); int sum=0; for(int i=1;i<=n;i++) { scanf("%d",num+i); int &temp=num[i]; dp1[i]=dp1[i-1]; if(sum<0)sum=temp; else sum+=temp; if(dp1[i]
      
       =1;i--) { int temp1=num[i]; dp2[i]=dp2[i+1]; if(sum<0)sum=temp1; else sum+=temp1; if(dp2[i]