前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >397. 最长上升连续子序列

397. 最长上升连续子序列

作者头像
和蔼的zhxing
发布2018-09-04 13:17:22
5510
发布2018-09-04 13:17:22
举报

给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列。) 样例 给定 [5, 4, 2, 1, 3], 其最长上升连续子序列(LICS)为 [5, 4, 2, 1], 返回 4. 给定 [5, 1, 2, 3, 4], 其最长上升连续子序列(LICS)为 [1, 2, 3, 4], 返回 4. 思路:两边遍历,利用动态规划思路,每当找到一个子序列比上一次找到的大,就存储当前的子序列,注意最后遍历结束的时候还要比较一次,因为一般写的程序是发现下降的时候来检查上升序列是否是最大的,如果序列本身在最后没有下降,不检查肯定是不合理的,一开始就错在这里了,到vs里调试了一下看了每步的结果才弄对,两次遍历: code:

代码语言:javascript
复制
 int longestIncreasingContinuousSubsequence(vector<int> &A) {
        int num_up=0;
        int num_down=0;
        int num_max[2]={0};
        if(A.empty())
        return 0;
        if(A.size()==1)
        return 1;
       
        for(int i=1;i<A.size();i++)  //一遍遍历
        {
            if(A[i]>=A[i-1])
            num_up++;
            if(A[i]<A[i-1])
            {
                if(num_up>num_max[0])
                num_max[0]=num_up;   //如果比上一次存的大,就赋值给最大值
                num_up=0;     //这个清零
            }
        }
        if(num_up>num_max[0])       
                num_max[0]=num_up;
                
       //上面这个if很重要,因为可能结尾之前一直上升,我们前面的程序是在下降的时候才检查这次的
       //上升值是否比以前存的大,但是可能一直没有下降就不检查了么?所以跳出循环以后这里还是要检查一次
        for(int i=A.size()-2;i>=0;i--)  //一遍遍历
        {
            if(A[i]>=A[i+1])
            num_down++;
            if(A[i]<A[i+1])
            {
                if(num_down>num_max[1])
                num_max[1]=num_down;
                num_down=0;
            }
        }
         if(num_down>num_max[1])
                num_max[1]=num_down;
        return (num_max[0]>num_max[1])?num_max[0]+1:num_max[1]+1;
    
        // write your code here
    }
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017.11.26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档