LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

题目描述

300 Longest Increasing Subsequence
https://leetcode-cn.com/problems/longest-increasing-subsequence/

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:
There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

---

相似题目

LeetCode.1143.Longest Common Subsequence 最长公共子序列LCS
LeetCode.718.Maximum Length of Repeated Subarray 最长公共子串/最长重复子数组
LeetCode.300.Longest Increasing Subsequence 最长上升子序列LIS

---

解题过程

动态规划

子序列是不需要连续的，我们知道了 nums[i] 之前所有比 nums[i] 小的子序列 0,…,j 的最长上升子序列长度，则再加 1 就是 0,…,i 的最长上升子序列长度。

设 lis[i] 是 nums[0…i] 的最长上升子序列的长度，则

$ lis[i] = max(lis[j]) + 1, 0 \leq j \leq i-1 且 nums[j] < nums[i] $

从前往后求出所有 lis[0…n-1] ，其中的最大值就是真个数组 nums 的 lis

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

private static class SolutionV2020 {
    public int lengthOfLIS(int[] nums) {
        if (null == nums) {
            return 0;
        }
        if (nums.length < 2) {
            return nums.length;
        }
        // lis[i] 表示 0, ... i-1 中 最长上升子序列的长度
        int[] lis = new int[nums.length];
        // lis 的最大值
        int max = 0;
        // 找 nums[i] 之前比 nums[i] 小的数中的 lis 最大值
        for (int i = 1; i < nums.length; i++) {
            boolean update = false;
            int preLessMax = 0;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] < nums[i]) {
                    update = true;
                    preLessMax = Math.max(preLessMax, lis[j]);
                }
            }
            if (update) {
                lis[i] = preLessMax + 1;
                max = Math.max(max, lis[i]);
            }
        }
        return max + 1;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_300_LongestIncreasingSubsequence.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_300_LongestIncreasingSubsequence.java

---