首页 > 代码库 > 【DP】最大连续子序列-hdu 1231
【DP】最大连续子序列-hdu 1231
题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=1231
算法参考：http://blog.163.com/wuguojin03@126/blog/static/17154113120109510946717/
状态：dp[i]:以i为结尾最长连续序列
初始状态：dp[i]=a[i]
状态转移：dp[i]=max{dp[i-1]+a[i]，a[i]}
要求最大的，只需从dp[i]找出最大值就行了
以本题输入样例 “ -2 11 -4 13 -5 -2 ” 为例：
序号: 0 1 2 3 4 5
a[]: -2 11 -4 13 -5 -2
dp[]: -2 11 7 20 15 13
观察dp[],终点即为 max：20，起点则为从max往前找最后一个不为负的数，即11
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 using namespace std; 5 6 const int MAXN=10010; 7 int a[MAXN],dp[MAXN]; 8 9 int main()10 {11 int n;12 while(cin>>n && n){13 int s=0,e=0;14 for (int i = 0; i < n; ++i){15 cin>>a[i];16 dp[i]=a[i];17 }18 for(int i=1;i<n;++i){19 if(dp[i-1]+a[i]>a[i])20 dp[i]=dp[i-1]+a[i];21 }22 int max=-1;23 for (int i = 0; i < n; ++i){24 if(max<dp[i]){25 max=dp[i];26 e=i;27 }28 }29 for(int i=e;i>=0;--i)30 if(dp[i]<0){31 s=i+1;32 break;33 }34 if(max<0)cout<<"0 "<<dp[0]<<" "<<dp[n-1]<<endl;35 else cout<<max<<" "<<a[s]<<" "<<a[e]<<endl;36 }37 return 0;38 }
【DP】最大连续子序列-hdu 1231
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。