【面试经典150 | 】最长递增子序列

Tag

【动态规划】【数组】

题目来源

300. 最长递增子序列

解题思路

方法一：动态规划

定义状态

dp[i] 表示以位置 i 对应整数为末尾的最长递增子序列的长度。

状态转移

我们从小到大计算 dp 数组的值，在计算 dp[i] 之前，我们已经计算出 dp[0], dp[1], ..., dp[i-1] 的值，有状态转移方程：

$$dp[i]=max(dp[i],dp[j]+1)，其中0\le j<i且nums[j]<nums[i]$$

在计算状态 dp[i] 时，更新答案 max_length。

base case

对于以 nums[i] 结尾的最长递增子序列，我们均初始化为 1。

最后返回

最后直接返回维护的最长递增子序列的长度 max_length。

实现代码

class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
		vector<int> dp(n + 1, 1);
		int max_length = 0;

        if(n <= 1) return n;
        
		for (int i = 1; i < nums.size(); ++i) {
			for (int j = 0; j < i; ++j) {
				if (nums[j] < nums[i]) {
					dp[i] = max(dp[i], dp[j] + 1);
				}
			}
			max_length = max(max_length, dp[i]);
		}
		return max_length;
	}
};

复杂度分析

时间复杂度：$O(n^2)$，$n$ 是数组 nums 的长度。我们一共需要计算 $O(n)$ 个状态，每个状态需要 $O(n)$ 的时间遍历 dp[0, ..., i-1] 的状态，所以时间复杂度为 $O(n^2)$。

空间复杂度：$O(n)$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。