一、最长上升子序列
300. 最长递增子序列
（一）初版代码
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> f(n + 1, 1); //初始化为1，因为每个数至少可以作为一个单独的序列int m = 1;//初始化为1，因为每个数至少可以作为一个单独的序列for (int i = 1; i <= n; i++) {for (int j = i - 1; j > 0; j--) {if (nums[j - 1] < nums[i - 1]) {f[i] = max(f[j] + 1, f[i]);m = max(m, f[i]);}}}return m;}
};复杂度分析
- 时间复杂度：O(n2)，其中 n 为 nums 的长度。
- 空间复杂度：O(n)。
易错点：
初始化问题：数组和max值都要初始化为1，因为每个数至少可以作为一个单独的序列。
（二）优化动态规划算法：贪心+二分查找
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> g;for (int i = 0; i < n; i++) {auto it = lower_bound(g.begin(), g.end(), nums[i]);if (it != g.end()) {*it = nums[i];} elseg.push_back(nums[i]);}return g.size();}
};复杂度分析
- 时间复杂度：O(nlogn)，其中 n 为 nums 的长度。
- 空间复杂度：O(n)。
二、买卖股票的最佳时机
121. 买卖股票的最佳时机
（一）暴力算法（超时）
class Solution {
public:int maxProfit(vector<int>& prices) {int n = (int)prices.size(), ans = 0;for (int i = 0; i < n; ++i){for (int j = i + 1; j < n; ++j) {ans = max(ans, prices[j] - prices[i]);}}return ans;}
};
复杂度分析
- 时间复杂度：O(n2)，其中 n 为 nums 的长度。
- 空间复杂度：O(1)。
（二）动态规划
#include <climits> // 引入INT_MAXclass Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int mcost = INT_MAX;int profit = 0;for (int i = 0; i < n; i++) {mcost = min(mcost, prices[i]);profit = max(profit, prices[i] - mcost);}return profit;}
};
复杂度分析
- 时间复杂度：O(n)，其中 n 为 nums 的长度。
- 空间复杂度：O(1)。
