首页 > 代码库 > 【两段连续不重合子序列和最大】 动态规划
【两段连续不重合子序列和最大】 动态规划
最大子序列
TimeLimit: 1 Second MemoryLimit: 32 Megabyte
Totalsubmit: 156 Accepted: 42
Description
给定一个N个整数组成的序列，整数有正有负，找出两段不重叠的连续子序列，使得它们中整数的和最大。两段子序列都可以为空。Input
多组输入，每组第一行为N，表示序列的长度；第二行为N个整数，表示输入序列。0<N<=1,000,000
Output
对于每组输入，输出一行，仅一个整数，表示最大的和。Sample Input
9
185 -580 -889 701 964 -878 353 -761 608
Sample Output
2273
Hint
样例输入序列的一种选择为：(701 964)和(608)，整数的范围为(-1000,1000)
#include <iostream>#include <cstdio>using namespace std;const int INF=1000005;int s[INF],lt[INF],rt[INF],dp[INF];int main(){ //freopen("in.txt","r",stdin); int i,n; while(cin >> n) { for (i=1;i<=n;i++)scanf("%d",&s[i]); dp[n+1]=dp[0]=-INF; lt[0]=rt[n+1]=-INF; for (i=1;i<=n;i++)//正向 { dp[i] = max(dp[i-1]+s[i],s[i]); } for (i=1;i<=n;i++) { lt[i] = max(dp[i],lt[i-1]);// lt[i] = dp[i]; } for (i=n;i>=1;i--) //逆向 { dp[i] = max(dp[i+1]+s[i],s[i]); } for (i=n;i>=1;i--) { rt[i] = max(dp[i],rt[i+1]);// rt[i] = dp[i]; } int sum=-INF;//枚举 for (i=1;i<=n;i++) { sum = max(sum,lt[i]+rt[i+1]); } if(sum<=0) cout <<‘0‘ <<endl; else printf("%d\n",sum); } return 0;}
【两段连续不重合子序列和最大】 动态规划
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。