LeetCode 300. 最长递增子序列

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 300. 最长递增子序列

思路分析

我们可以使用动态规划来解决这个问题。具体思路如下：

创建一个数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

初始化 dp 数组，每个位置的初始值为 1，因为每个元素至少可以形成一个长度为 1 的递增子序列。

使用双重循环，外层循环遍历每个元素，内层循环遍历当前元素之前的所有元素：

如果 nums[j] < nums[i]，则可以将 nums[i] 加入到以 nums[j] 结尾的递增子序列中，更新 dp[i] 为 max(dp[i], dp[j] + 1)。

最后，返回 dp 数组中的最大值，即为最长递增子序列的长度。

参考代码

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
	dp := make([]int, len(nums))
	for i := range dp {
		dp[i] = 1 // 每个元素至少可以形成一个长度为 1 的递增子序列
	}

	res := 1

	for i := 1; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		res = max(res, dp[i])
	}

	return res
}

时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。需要两层循环来遍历数组。

空间复杂度：O(n)，用于存储 dp 数组。

func lengthOfLIS(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
	dp := make([]int, len(nums))
	dp[0] = 1
	res := 1
	for i := 1; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		res = max(res, dp[i])
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

🍏 点击查看 Java 题解

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

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/87131039