300最长上升子序列

小咪咪 2023-02-25 07:14 26阅读 0赞

## 一、前言 ##

分类：动态规划。

问题来源LeetCode 300 难度：中等。

问题链接：[https://leetcode-cn.com/problems/longest-increasing-subsequence/][https_leetcode-cn.com_problems_longest-increasing-subsequence]

## 二、题目 ##

给定一个无序的整数数组，找到其中最长上升子序列的长度。

**示例1：**

输入: [10,9,2,5,3,7,101,18]
    输出: 4 
    解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

## 三、思路 ##

### 3.1 方法一：动态规划 ###

动态规划递推公式：dp\[i\]=max(dp\[j\])+1,其中0≤j<i且num\[j\]<num\[i\]。

**复杂度分析：**

*  时间复杂度：O(n^2)
 *  空间复杂度：O(n)

以输入序列 \[10,9,2,5,3,7,101,18\]为例，数组变化如下图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

### 3.2 方法二：贪心 + 二分查找 ###

贪心法 + 二分法：使用数组来进行上升序列的积累。如果上升则积累（append），如果下降，则通过二分法找到探索元素的位置进行替换（不改变数组的长度）。最终返回数组的长度。

设当前已求出的最长上升子序列的长度为 len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums\[i\] 时：

*  如果 nums\[i\]>dp\[len\] ，则直接加入到 dp 数组末尾，并更新 len=len+1；
 *  否则，在 d 数组中二分查找，在 dp 数组中找到第一个大于或等于 nums\[i\] 的数 dp\[k\] ，并更新 d\[k\]=nums\[i\]。

**复杂度分析：**

*  时间复杂度：O(nlogn)
 *  空间复杂度：O(n)

以输入序列 \[10,9,2,5,3,7,101,18\]为例，数组变化如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1][]

最终得到最大递增子序列长度为 4。

## 四、总结 ##

*  多理解递推公式和递推公式怎样获取。
 *  一次扫描，如果对扫描的数据有顺序要求，能不能对其进行排序。

## 五、编码实现 ##

//==========================================================================
    /*
    * @file    : 300_LengthOfLIS.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107269090
    * @author  : niebingyu
    * @date    : 2020/07/10
    * @title   : 300.最长上升子序列
    * @purpose : 给定一个无序的整数数组，找到其中最长上升子序列的长度。
    *
    * 示例 1：
    * 输入: [10,9,2,5,3,7,101,18]
    * 输出: 4
    * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：中等
    * 链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_LENGTHOFLIS namespace NAME_LENGTHOFLIS {
    #define NAMESPACE_LENGTHOFLISEND }
    NAMESPACE_LENGTHOFLIS
    
    // 动态规划
    // 递推公式：dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
    // 时间复杂度：O(n^2), 空间复杂度：O(n)
    class Solution1 
    {
    public:
        int lengthOfLIS(vector<int>& nums) 
        {
            int n=(int)nums.size();
            if (n == 0) return 0;
            vector<int> dp(n, 0);
            int maxLen = 1;
            for (int i = 0; i < n; ++i) 
            {
                dp[i] = 1;
                for (int j = 0; j < i; ++j) 
                {
                    if (nums[j] < nums[i])
                    {
                        dp[i] = max(dp[i], dp[j] + 1);
                        maxLen = max(maxLen, dp[i]);
                    }
                }
            }
            
            //return *max_element(dp.begin(), dp.end());
            return maxLen;
        }
    };
    
    // 动态规划
    // dp[i] = max(dp[j]) + 1, 其中 0 ≤ j < i 且 num[j] < num[i] 
    class Solution
    {
    public:
    	// 返回不小于目标值的位置 
        int search(vector<int> & nums, int target)
        {
            int l = 0;
            int r = nums.size() - 1;
            while(l < r)
            {
                int mid = (r + l) / 2;
                if(target == nums[mid])
                   return mid;
                else if(target > nums[mid])
                   l = mid + 1;
                else if(target < nums[mid])
                   r = mid;
            }
            return l;
        }
    
        int lengthOfLIS(vector<int>& nums) 
        {
            int len = nums.size();
            vector<int> dp;
            if(len <= 0) return 0;
            dp.push_back(nums[0]);
            for(int i = 1;i < len;i++)
            {
                if(nums[i] > dp[dp.size() - 1])
                    dp.push_back(nums[i]);
                else
                {
                     //auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
                    //*it = nums[i];
    
                    int p = search(dp,nums[i]);
                    dp[p] = nums[i];
                }
            }
    
             return dp.size();
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<int>& nums, int expect)
    {
        Solution_1 s1;
        int result1 = s1.lengthOfLIS(nums);
        Solution_2 s2;
        int result2 = s2.lengthOfLIS(nums);
        if (expect == result1 && expect == result2)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. expect:" << expect << ", result1:" <<result1 << ", result2:" << result2 << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<int> nums = { 10,9,2,5,3,7,101,18 };
        int expect = 4;
        
        test("Test1()", nums, expect);
    }
    
    void Test2()
    {
        vector<int> nums = { 10,11,1,2,3,12,13,4 };
        int expect = 5;
    
        test("Test2()", nums, expect);
    }
    
    NAMESPACE_LENGTHOFLISEND
    // 测试 用例 END
    //
    
    void LengthOfLIS_Test()
    {
        NAME_LENGTHOFLIS::Test1();
        NAME_LENGTHOFLIS::Test2();
    }

**执行结果：**

![20200710214218163.png][]

[https_leetcode-cn.com_problems_longest-increasing-subsequence]: https://leetcode-cn.com/problems/longest-increasing-subsequence/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230209/2d0a75fe195f46feb053b50394fc770f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200710213051280.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE=,size_16,color_FFFFFF,t_70
[20200710214218163.png]: https://img-blog.csdnimg.cn/20200710214218163.png