300. Longest Increasing Subsequence (Medium)——最长递增子序列

小灰灰 2023-05-29 09:20 44阅读 0赞

> ### 前言： ###

本题目为动态规划思想的一道典型例题——最长递增子序列。

> ### 题目 ： ###

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

示例:

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

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

> ### 解题算法：  ###

# 最长递增子序列 #

已知一个序列 \{S1, S2,...,Sn\}，取出若干数组成新的序列 \{Si1, Si2,..., Sim\}，其中 i1、i2 ... im 保持递增，即新序列中各个数仍然保持原数列中的先后顺序，称新序列为原序列的一个 **子序列** 。

如果在子序列中，当下标 ix > iy 时，Six > Siy，称子序列为原序列的一个 **递增子序列** 。

定义一个数组 dp 存储最长递增子序列的长度，dp\[n\] 表示以 Sn 结尾的序列的最长递增子序列长度。对于一个递增子序列 \{Si1, Si2,...,Sim\}，如果 im < n 并且 Sim < Sn，此时 \{Si1, Si2,..., Sim, Sn\} 为一个递增子序列，递增子序列的长度增加 1。满足上述条件的递增子序列中，长度最长的那个递增子序列就是要找的，在长度最长的递增子序列上加上 Sn 就构成了以 Sn 为结尾的最长递增子序列。因此 dp\[n\] = max\{ dp\[i\]+1 | Si < Sn && i < n\} 。

因为在求 dp\[n\] 时可能无法找到一个满足条件的递增子序列，此时 \{Sn\} 就构成了递增子序列，需要对前面的求解方程做修改，令 dp\[n\] 最小为 1，即：

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

对于一个长度为 N 的序列，最长递增子序列并不一定会以 SN 为结尾，因此 dp\[N\] 不是序列的最长递增子序列的长度，需要遍历 dp 数组找出最大值才是所要的结果，max\{ dp\[i\] | 1 <= i <= N\} 即为所求。

> ### 思路： ###

定义一个数组dp来存储到第num\[i\]个元素为止，最大的子序列长度（0<= i <=nums.length）。对于一个元素num\[i\]，计算包括它之前的最大自增子序列长度的办法是：先定义一个max，默认值为1，再拿该元素num\[i\]与它之前的所有元素做比，如果发现它大于前边的某一元素num\[j\]，就让该下标为j的元素的最长递增子序列+1（dp\[j\] + 1），然后与max相比取最大值，最终得出的max就是num\[i\]的最长递增子序列。

> ###  代码： ###

public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            int max = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    max = Math.max(max, dp[j] + 1);
                }
            }
            dp[i] = max;
        }
        return Arrays.stream(dp).max().orElse(0);
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jYW1vLmdpdGh1YnVzZXJjb250ZW50LmNvbS9jNmI3NmI2NWMxODgwYTUwN2JmMWNiMDI1MDQ1NjEyMWRiNTdhMWFiLzY4NzQ3NDcwNzMzYTJmMmY2MzczMmQ2ZTZmNzQ2NTczMmQzMTMyMzUzNjMxMzAzOTM3MzkzNjJlNjM2ZjczMmU2MTcwMmQ2Nzc1NjE2ZTY3N2E2ODZmNzUyZTZkNzk3MTYzNmM2Zjc1NjQyZTYzNmY2ZDJmNjU2NTM5MzkzNDY0NjEzNDJkMzA2NjYzMzcyZDM0MzQzMzY0MmQ2MTYzMzUzNjJkNjMzMDM4NjM2MTY2MzAzMDYxMzIzMDM0MmU2YTcwNjc?x-oss-process=image/format,png
[format_png 1]: https://camo.githubusercontent.com/c6b76b65c1880a507bf1cb0250456121db57a1ab/68747470733a2f2f63732d6e6f7465732d313235363130393739362e636f732e61702d6775616e677a686f752e6d7971636c6f75642e636f6d2f65653939346461342d306663372d343433642d616335362d6330386361663030613230342e6a7067