Leetcode：300. Longest Increasing Subsequence（最大增长序列）

╰+攻爆jí腚メ 2022-04-05 15:48 158阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录:**

题目描述：

方法1：

Java实现方法：（利用动态规划和二分查找的方式）

python实现方式：

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

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

示例:

输入: [10,9,2,5,3,7,101,18]
    输出: 4

解释: 最长的上升子序列是 \[2,3,7,101\]，它的长度是 4。  
说明:

可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。  
你算法的时间复杂度应该为 O(n2) 。

来源：力扣（LeetCode）

--------------------

## 方法1： ##

--------------------

**解题思路：**  
**降低复杂度切入点：** 解法一中，遍历计算 dp 列表需 O(N)，计算每个 dp\[k\]\] 需 O(N)。

动态规划中，通过线性遍历来计算 dp 的复杂度无法降低；  
每轮计算中，需要通过线性遍历 \[0,k) 区间元素来得到 dp\[k\] 。我们考虑：是否可以通过重新设计状态定义，使整个 dp为一个**排序列表**；这样在计算每个 dp\[k\]时，就可以通过二分法遍历 \[0,k) 区间元素，将此部分复杂度由 O(N) 降至 O(logN)。

--------------------

**设计思路：**

**新的状态定义：**  
我们考虑维护一个列表 tails，其中每个元素 tails\[k\] 的值代表 长度为 k+1 的子序列尾部元素的值。  
如 \[1,4,6\] 序列，长度为 1,2,3 的子序列尾部元素值分别为 tails = \[1,4,6\]。  
**状态转移设计：**  
设常量数字 N，和随机数字 xx，我们可以容易推出：当 N 越小时，N<x的几率越大。例如： N=0肯定比 N=1000 更可能满足 N<x。在遍历计算每个 tails\[k\]，不断更新长度为 \[1,k\]的子序列尾部元素值，始终保持每个尾部元素值最小 （例如 \[1,5,3\]， 遍历到元素 5 时，长度为 2 的子序列尾部元素值为 5；当遍历到元素 3 时，尾部元素值应更新至 3，因为 3 遇到比它大的数字的几率更大）。**tails 列表一定是严格递增的**： 即当尽可能使每个子序列尾部元素值最小的前提下，子序列越长，其序列尾部元素值一定更大。  
**反证法证明：** 当 k < i，若 tails\[k\] >= tails\[i\]，代表较短子序列的尾部元素的值 > 较长子序列的尾部元素的值。这是不可能的，因为从长度为 i 的子序列尾部倒序删除 i-1 个元素，剩下的为长度为 k 的子序列，设此序列尾部元素值为 v，则一定有 v<tails\[i\] （即长度为 k 的子序列尾部元素值一定更小）， 这和 tails\[k\]>=tails\[i\]矛盾。  
既然严格递增，每轮计算 tails\[k\] 时就可以使用二分法查找需要更新的尾部元素值的对应索引 i。  
**算法流程：**

**状态定义：**

--------------------

tails\[k\]的值代表 长度为k+1 子序列 的尾部元素值。  
**转移方程**： 设 res 为 tails 当前长度，代表直到当前的最长上升子序列长度。设 j∈\[0,res)，考虑每轮遍历 nums\[k\] 时，通过二分法遍历 \[0,res) 列表区间，找出 nums\[k\]的大小分界点，会出现两种情况：

**区间中存在** tails\[i\] > nums\[k\] ： 将第一个满足 tails\[i\] > nums\[k\] 执行 tails\[i\] = nums\[k\] ；因为更小的 nums\[k\] 后更可能接一个比它大的数字（前面分析过）。  
**区间中不存在** tails\[i\] > nums\[k\] ： 意味着 nums\[k\] 可以接在前面所有长度的子序列之后，因此肯定是接到最长的后面（长度为 res ），新子序列长度为 res + 1。  
**初始状态：**

令 tails列表所有值 =0。  
**返回值：**

返回 res ，即最长上升子子序列长度。

**流程图：**

![format_png][]![format_png 1][]

### ![format_png 2][]![format_png 3][] ###

### ![format_png 4][]![format_png 5][] ###

### ![format_png 6][]![format_png 7][] ###

### ![format_png 8][]![format_png 9][] ###

--------------------

### Java实现方法：（利用动态规划和二分查找的方式） ###

/**
         * 最大增数组
         *
         * @param nums 数字
         * @return 增数组个数
         */
        private int lengthOfLIS1(int[] nums) {
            int[] dp = new int[nums.length];
            int len = 0;
            for (int num : nums) {
                int i = Arrays.binarySearch(dp, 0, len, num);
                if (i < 0) {
                    i = -(i + 1);
                }
                dp[i] = num;
                if (i + 1 > len) {
                    len = i + 1;
                }
            }
            return len;
        }

时间复杂度： O（NlogN )  
空间复杂:O（N）

--------------------

### python实现方式： ###

from typing import List
    import numpy as np
    
    
    def length_of_LIS(nums: List[int]):
        '''
            获取最大递增数组
        Args:
            nums: 数组
        Returns:
            递增数组个数
        '''
        dp = np.zeros(len(nums))
        length = 0
        for num in nums:
            i = binary_search(nums, 0, length, num)
            if i < 0:
                i = -(i + 1)
            dp[i] = num
            if i + 1 > length:
                length = i + 1
        return length
    
    
    def binary_search(arr: List[int], l: int, r: int, x: int):
        '''
            二分查找
        Args:
            arr: 输入数组
            l: 开始下标
            r: 结束下标
            x: 要查找的数
        Returns:
            要查找数的下标
        '''
        if r >= l:
            mid = int(l + (r - l) / 2)  # 防止溢出
            if arr[mid] == x:
                return mid
            elif arr[mid] > x:
                return binary_search(arr, l, mid - 1, x)
            else:
                return binary_search(arr, mid + 1, r, x)
        else:
            return -1  # 不存在

时间复杂度：O(n.logn)

空间复杂度：O(n)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzgyMWZlOTA0Y2E3ZmNiYmYzMDk0MDdhZDdlNDE5NTJiMjlkNmIxZDY5ODljNDcxZjQzNThlN2UxZGM1MmU0MTYtUGljdHVyZTEucG5n?x-oss-process=image/format,png
[format_png 1]: /images/20220405/d640ebb557604d8fafc57a7492a12859.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzU3Nzc3MDQwYzY2ZjFjYTg3NDhhYzJkNmVhZWM5MzI1NmYxYTQ1OGFkMmEyMTllOWQxNjZlZTlhZWY2MDhmNjYtUGljdHVyZTMucG5n?x-oss-process=image/format,png
[format_png 3]: /images/20220405/78601eb35ded4d928239342309d70b41.png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tL2M5OWIzZWVjYTgyN2EyZjFjNWU1NWYxNTEzMWU4MWY0NjMxNTBlOWRiNjI5MDY3MjI0NTcyNjRmMTMyODAzMmItUGljdHVyZTUucG5n?x-oss-process=image/format,png
[format_png 5]: /images/20220405/e5dbd21fe6934ab5a5c0893a0f3a8ca3.png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzRlYjA5NmJmMDFlMWMxODc5YzJiMTdhMWMyOTgzNDFhNGRlNGY0OGQ5MjkyMTI3MDIwNzgxNDQ4YzRmNGRjNzgtUGljdHVyZTcucG5n?x-oss-process=image/format,png
[format_png 7]: /images/20220405/0bb318d538144bddbe58102461dcc078.png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tL2M4ZjZhODU0M2E2MjdlMmEyZDA3ZTFiNmQ4YjNmMTQyZTBiODg0NGZkNjM5YWNiNTUzYTk2NTRkNTY0ZjRhOGItUGljdHVyZTkucG5n?x-oss-process=image/format,png
[format_png 9]: /images/20220405/3c48ab8dc616463998d8836b3ddcc3c7.png
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode