Version: Next

300.最长递增子序列

最长递增子序列 Longest Increasing Subsequence LIS
难度 中等
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
进阶：
你可以设计时间复杂度为 O(n2) 的解决方案吗？
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

动态规划

对于 [10, 2, 2, 5, 1, 7, 101, 18]

定义状态：dp(i) 是以 nums[i] 结尾的最长上升子序列的长度
以nums[0] = 10 结尾的最长上升子序列是 [10]，则 dp[0] = 1
以nums[1] = 2 结尾的子序列是 [10, 2] 和 [2]，最长上升子序列为 [2] ，则 dp[1] = 1
以nums[2] = 2 结尾的最长上升子序列是 [2]，则 dp[2] = 1
以nums[3] = 5 结尾的最长上升子序列是 [2, 5]，则 dp[3] = dp[2] + 1 = 2
以nums[4] = 1 结尾的最长上升子序列是 [1]，则 dp[4] = 1
以nums[5] = 7 结尾的最长上升子序列是 [2, 5, 7]，则 dp[5] = dp[3] + 1 = 3
以nums[6] = 101 结尾的最长上升子序列是 [2, 5, 7, 101]，则 dp[6] = dp[5] + 1 = 4
以nums[7] = 18 结尾的最长上升子序列是 [2, 5, 7, 18]，则 dp[7] = dp[5] + 1 = 4
初始状态（边界）：对于以任意一个元素结尾的上升子序列，其默认长度都为 1
状态转移方程
对于当前元素 nums[i]，遍历当前元素之前所有元素，目的是找到先前所有元素 dp 值的 最大值
当前 nums[i] 与先前的每一个元素 nums[j] 比较，nums[i] > nums[j]，说明当前 nums[i] 可以接在以 nums[j] 结尾的最长上升子序列后面，形成一个 比 dp[j] 更长的上升子序列长度为 dp[j + 1]
还要确保 nums[i] 接到 nums[j] 后面形成的子序列不会比当前的最长子序列还短，即确保dp[j + 1] > dp[i]，才更新 dp[i] 的值，总是确保 dp[i]的值更大，即 dp[i] = max{ dp[i], dp[j] + 1}
否则，说明 nums[i] <= nums[j]，不能把 nums[i] 接在 nums[j] 后面，则dp[i] = 1
一直记录最大的那个 dp[i]，即为所求解

public class _300最长上升子序列 {
    public static int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int[] dp = new int[nums.length];

        dp[0] = 1;
        int max = dp[0];

        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1; // 以每个元素结尾。默认子序列长度都为 1
            for (int j = 0; j < i; j++) { // 遍历当前值之前所有的元素
                // 当前值 比 先前某个元素大
                // 说明 当前值i 可以接在 以先前值j结尾的 上升子序列后面
                // 还要确保接在j这个元素的子序后面不会比现在还短
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            // 一致记录最大的 dp[i]
            max = Math.max(max, dp[i]);
        }

        return max;
    }

    public static void main(String[] args) {
        int[] nums1 = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] nums2 = {0, 1, 0, 3, 2, 3};
        int[] nums3 = {7, 7, 7, 7, 7, 7, 7};

        int res1 = lengthOfLIS(nums1); // expect 4
        int res2 = lengthOfLIS(nums2); // expect 4
        int res3 = lengthOfLIS(nums3); // expect 1

        System.out.println("res1 = " + res1);
        System.out.println("res2 = " + res2);
        System.out.println("res3 = " + res3);
    }
}

300.最长递增子序列#

动态规划#

300.最长递增子序列

动态规划