一、最長上升子序列

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)。