HDU–1231 : 最大连续子序列 (DP求连续子序列最大和)

不管现实多么惨不忍睹,都要持之以恒地相信,这只是黎明前短暂的黑暗而已。不要惶恐眼前的难关迈不过去,不要担心此刻的付出没有回报,别再花时间等待天降好运。真诚做人,努力做事!你想要的,岁月都会给你。HDU–1231 : 最大连续子序列 (DP求连续子序列最大和),希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

1. 题目源地址:http://acm.hdu.edu.cn/showproblem.php?pid=1231

2. 动态规划方程:

状态:dp[i]:以i为结尾最长连续序列

初始状态:dp[0]=num[0]

状态转移:dp[i]=max{dp[i-1]+num[i],num[i]} (比较已有序列和新元素的和新元素本身的大小关系,取较大的)

 
 
要求最大的,只需从dp[]找出最大值就行了
举例说明:序列 {-2, 11, -4, 13, -5, -2}
1.初始状态时:dp[0]=num[0]=-2
2.状态转移:要求dp[1],则需要比较dp[0]+num[1]与num[1]的大小关系。
由于 dp[0]+num[1]=-2+11=9,而num[1]=11。所以需要抛弃序列之前保留的值,从num[1]开始重新计数。
故状态转移为:dp[1]=num[1]=11
3.源代码:
#include<iostream>
using namespace std;
int main()
{
    int N,i,j,pos;
    int num[10010],dp[10010];
    int start[10010];//用于记录序列的开始元素 
    
    while(cin>>N && N)
    {
       for(i=0;i<N;i++)
          cin>>num[i];
       
       int flag=1; //如果全为负数,输出0以及第一个和最后一个元素 
       for(i=0;i<N;i++)
       {
          if(num[i]>=0)
          {
             flag=0;
             break;
          }
       }
       if(flag)   
       {
          cout<<0<<" "<<num[0]<<" "<<num[N-1]<<endl; 
          continue; 
       } 
       
       dp[0]=num[0];
       start[0]=0;
       for(i=1;i<N;i++)
       {
          if(dp[i-1]+num[i]>=num[i])//若符合动态规划方程。注意:这里是大于等于! 
          {
             dp[i]=dp[i-1]+num[i];
             start[i]=start[i-1];//序列开始元素的值不变 
          }
          else
          {
             dp[i]=num[i];
             start[i]=i;//序列开始元素的值改变 
          }
       }
       
       int max=-1;//注意:这里max注意取值 
       for(i=0;i<N;i++)
       {
          if(dp[i]>max)
          {
             max=dp[i];
             pos=i;//start[pos]中记录了该序列的开始位置,pos为序列的结束 
          }
       }
       cout<<max<<" "<<num[start[pos]]<<" "<<num[pos]<<endl;
    }
    return 0;
} 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/163027.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!