76. 最长上升子序列动态规划+二分查找

和蔼的zhxing

发布于 2018-09-04 11:20:40

1.3K0

发布于 2018-09-04 11:20:40

文章被收录于专栏：和蔼的张星的图像处理专栏

给定一个整数序列，找到最长上升子序列（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;
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018.03.05 ，如有侵权请联系 cloudcommunity@tencent.com 删除

java