簡單記錄學習~

給你一個整數數組?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^2)的動態規劃解法和O(nlogn)的貪心+二分查找的解法

dp算法：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;vector<int> dp(n, 1);  // 每個位置初始化為 1// 遍歷每一個位置 ifor (int i = 0; i < n; ++i) {// 遍歷每一個比 i 小的位置 jfor (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) {  // 如果可以連接dp[i] = max(dp[i], dp[j] + 1);  // 狀態轉移}}}return *max_element(dp.begin(), dp.end());  // 返回 dp 數組中的最大值
}int main() {vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};  // 示例輸入cout << "Length of Longest Increasing Subsequence: " << lengthOfLIS(nums) << endl;return 0;
}

貪心＋二分查找：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.empty()) return 0;vector<int> tails;  // 用來記錄每個長度的遞增子序列的末尾元素for (int num : nums) {// 二分查找：尋找 num 應該插入的位置auto it = lower_bound(tails.begin(), tails.end(), num);// 如果 num 小于等于 tails 中某個值，就替換掉它if (it != tails.end()) {*it = num; // 這一步嚴格保證了我們在計算的是遞增子序列且是按照原數組的順序得到的遞增子序列} else {// 如果 num 大于 tails 中的所有值，添加到末尾tails.push_back(num);}}return tails.size();  // 最終的 tails 長度就是最長遞增子序列的長度
}};