首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >动态规划应用--最长递增子序列 LeetCode 300

动态规划应用--最长递增子序列 LeetCode 300

作者头像
Michael阿明
发布于 2021-02-20 10:53:29
发布于 2021-02-20 10:53:29
7570
举报

​

1. 问题描述

有一个数字序列包含n个不同的数字,如何求出这个序列中的最长递增子序列长度?比如2,9,3,6,5,1,7这样一组数字序列,它的最长递增子序列就是2,3,5,7,所以最长递增子序列的长度是4。

https://leetcode-cn.com/problems/longest-increasing-subsequence/

2. 解题思路

2.1 动态规划

  • 假设在包含 i-1 下标数字时的最大递增子序列长度为 maxLen(i-1),那么下标为 i 时的 maxLen(i)需要考虑前面所有的状态,
  • 如果 aj < ai (0 <= j < i),则 maxleni = max(maxlenj+1 | (0 <= j < i));
  • 如果 aj >= ai (0 <= j < i),则 maxleni = 1;

借一张动图说明

代码语言:javascript
复制
class Solution 
{
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n = nums.size();
        if(n == 0)
            return 0;
        int maxlen[n], ans;
        int i, j;
        for(i = 0; i < n; ++i)
            maxlen[i] = 1;//至少为1,自己
        for(i = 1; i < n; ++i)
        {
        	ans = 1;
            for(j = 0; j < i; ++j)
            {
            	if(nums[i] > nums[j] && maxlen[j]+1 > ans)
            	{
            		ans = maxlen[j]+1;
            		maxlen[i] = ans;
            	} 
        	}
        }
        for(ans = 1, i = 0; i < n; ++i)
        {
        	if(maxlen[i] > ans)//取最大值
        		ans = maxlen[i];
        }
        return ans;
    }
};
代码语言:javascript
复制
class Solution {	//2020.3.14
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        int i, j, n = nums.size(),maxlen = 1;
        vector<int> dp(n,1);
        for(i = 1; i < n; ++i)
        {
            for(j = i-1; j >= 0; --j)
            {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j]+1);
            }
            maxlen = max(maxlen, dp[i]);
        }
        return maxlen;
    }  
};

2.2 二分查找

  • 参考官方的解答
  • dpi 表示长度为 i+1 的子序的最后一个元素的 最小数值
  • 遍历每个 numsi,找到其在dp数组中的位置(大于等于 numsi 的第一个数),将他替换成较小的

以输入序列 0, 8, 4, 12, 2 为例:

第一步插入 0,dp = 0

第二步插入 8,dp = 0, 8

第三步插入 4,dp = 0, 4

第四步插入 12,dp = 0, 4, 12

第五步插入 22,dp = 0, 2, 12

代码语言:javascript
复制
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        int i, l, r, n = nums.size(), maxlen = 1, idx;
        vector<int> dp(n);
        dp[0] = nums[0];
        for(i = 1; i < n; ++i)//遍历每个数
        {
            l = 0, r = maxlen-1;
            idx = bs(dp,l,maxlen,nums[i],maxlen);
			//二分查找nums[i] 在dp中的位置
            if(idx == maxlen)//nums[i] 是最大的
            {
                dp[idx] = nums[i];
                maxlen++;
            }
            else//不是最大的,更新 dp[i] 里的数为较小的
                dp[idx] = min(dp[idx], nums[i]);
        }
        return maxlen;
    }  

    int bs(vector<int> &dp, int l, int r, int& target, int& maxlen)
    {	//二分查找nums[i] 在dp中的位置, 第一个大于等于 nums[i] 的
        int mid;
        while(l <= r)
        {
            mid = l + ((r-l)>>1);
            if(dp[mid] < target)
                l = mid+1;
            else
            {
                if(mid == 0 || dp[mid-1] < target)
                    return mid;
                else
                    r = mid-1;
            }
        }
        return maxlen;//没有找到,nums[i] 最大,放最后
    }
};
  • 基于上面的想法,直接用 treeset 可以简化代码
代码语言:javascript
复制
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        set<int> s;
        for(auto& n : nums)
        {
            if(s.count(n))
                continue;
            else
            {
                auto it = s.upper_bound(n);//n的上界
                if(it == s.end())//没有比我大的
                    s.insert(n);
                else//有比我大的
                {
                    s.erase(it);//删除比我大的
                    s.insert(n);//换成我
                }
            }
        }
        return s.size();
    }
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/07/26 ,如有侵权请联系 cloudcommunity@tencent.com 删除
目录
  • ​
  • 1. 问题描述
  • 2. 解题思路
    • 2.1 动态规划
    • 2.2 二分查找
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档