LeetCode 300.最长递增子序列(中等)

题目描述

给你一个整数数组 ​​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

提示

进阶

你能将算法的时间复杂度降低到 ​​O(n log(n))​​ 吗?

题目分析

这道动态规划问题我们可以采用以下的解决方案，创建一个 ​​dp​​​ 数组，其中 ​​dp[i]​​​ 表示以第 ​​i​​​ 个位置结尾的子数组的最长递增子序列长度。同时，维护一个最长递增子序列长度变量，在遍历时不断更新最大值。遍历时，对于每一个位置 ​​i​​​ ，如果其之前的某个位置 ​​j​​​ 所对应的数字小于位置 ​​i​​​ 所对应的数字，则我们可以获得一个以 ​​i​​​ 结尾的、长度为 ​​dp[j]+ 1​​ 的最长递增子序列。

题解

执行用时: 59 ms

内存消耗: 41.1 MB

class Solution {
    public int lengthOfLIS(int[] nums) {
        // 获取数组长度
        int length = nums.length;
        // 如果长度为 1 返回 1
        if (length == 1) {
            return 1;
        }
        // 最长递增子序列长度
        int max = 1;
        // 创建 dp 数组
        int[] dp = new int[length];
        // dp 数组初始化
        for (int i = 0; i < length; ++i) {
            dp[i] = 1;
        }
        // 遍历数组
        for (int i = 0; i < length; ++i) {
            // 确定 i 位置最长递增子序列长度
            for (int j = 0; j < i; ++j) {
                // 如果递增
                if (nums[i] > nums[j]) {
                    // 更新 dp[i] 为 dp[i] 与 dp[j] + 1（当前元素） 最大值
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 更新 最长递增子序列长度
            max = Math.max(dp[i], max);
        }
        // 返回最长递增子序列长度
        return max;
    }
}

题目来源:力扣(LeetCode)