76. 最长上升子序列

给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。
说明
最长上升子序列的定义:
最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列,这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
样例
给出 [5,4,1,2,3],LIS 是 [1,2,3],返回 3
给出 [4,2,4,5,3,7],LIS 是 [2,4,5,7],返回 4
挑战
要求时间复杂度为O(n^2) 或者 O(nlogn)

动态规划+二分查找

模拟一个堆栈,遍历数组,我们先把第一个数放入堆栈,然后从第二个数开始遍历数组,如果这个数大于栈顶,则入栈,如果小于栈顶,则替换掉栈中第一个大于此数的那个数(这里可以用二分查找的方法,因为入栈的时候就已经排序)。
简单举个例子:

有数组:
6 1 3 5 4 3 5
遍历的话:
6                                       
1                                 //6大于1,替换
1 3                              //3大与1,入栈
1 3 5                           //5大于3,入栈
1 3 4                           //5是大于4的第一个,入栈
1 3 4                           //替换掉3,和不替换是一样的结果
1 3 4 5                        //5大于栈顶,入栈
end                          //结束,最长上升子序列为4个数,

在<algorithm>头文件里,有用在STL中查找第一个大于目标数字迭代器的算法,用这个函数当然是很简单的啦!

template<class ForwardIterator, class Type>
   ForwardIterator lower_bound(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _Val
   );

参数是两个正向迭代器,表示查找范围,目标数字是_Val,返回一个指向第一个大于等于目标数字的数字的迭代器。这个函数效率肯定是高的。
为了练习我还是想把二分查找的写一下,这样一写还是发现了一些问题,所以想把二分查找这里总结一下,放在另外一篇文章中。
这个题到这里就结束了,代码:

int longestIncreasingSubsequence(vector<int> &nums) {
        if(nums.size()==0)
        return 0;
        
        vector<int>  res;
        res.push_back(nums[0]);
        for(int i=1;i<nums.size();i++)
        {
           if(nums[i]>*(res.end()-1))
           res.push_back(nums[i]);
           else
           {
              //auto pos=lower_bound(res.begin(), res.end(), nums[i]);
              // cout<<*pos<<endl;
              //*pos=nums[i];
             
              Insert(nums[i],res);
           }
        }
    
    
        return res.size();
        // write your code here
    }
    
    void Insert(int num,vector<int> &vec)
    {
        auto beg=vec.begin();
        auto end=vec.end()-1;
        vector<int>::iterator mid;
        while(beg<=end)
        {
            mid=beg+(end-beg)/2;
            if(num<*mid)
            {
                end=mid-1;
            }
            else if(num>*mid)
            {
                beg=mid+1;
            }
            else return;      //如果查找到,则替换
        }
        
        if(num>*mid)         //如果大于mid,就在其后插入
        *(mid+1)=num;
        else 
        *mid=num;
    }
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,743评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,296评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,285评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,485评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,581评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,821评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,960评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,719评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,186评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,516评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,650评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,329评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,936评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,757评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,991评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,370评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,527评论 2 349

推荐阅读更多精彩内容

  • 描述 给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。 说明 最长上升子序列的定义:最长上升子序...
    6默默Welsh阅读 681评论 1 0
  • Lua 5.1 参考手册 by Roberto Ierusalimschy, Luiz Henrique de F...
    苏黎九歌阅读 13,764评论 0 38
  • 一、Java 简介 Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计...
    子非鱼_t_阅读 4,160评论 1 44
  • 给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。 说明 最长上升子序列的定义: 最长上升子序列问...
    Arnold134777阅读 1,003评论 0 0
  • 《生产力与生产模式谁更重要》如今,很多企业都很卖命,做得很刻苦,也很累。但是,也有不少企业只顾欣赏自己的产品,切忽...
    cb9fa4682249阅读 305评论 2 0