題目（鏈接）
給你一個整數陣列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
提示：
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
題解
思路：
- 動態規劃
- 每次考慮以第
i個數字結尾的最長上升子序列， - 狀態轉移：
f[i] = max(f[i], f[j] + 1)，f[j]表示以第j個數結尾的上升子序列的個數（j < i），每次有小于第i個數的數字時，就需要更新一次f[i]，
code:
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int f[n + 10];
for (int i = 1; i <= n; i ++){
f[i] = 1; // 只有nums[i]一個數的情況
for (int j = 1; j < i; j ++){
if (nums[j - 1] < nums[i - 1]){
f[i] = max(f[i], f[j] + 1); // 狀態轉移
}
}
}
// 求最長的個數
int res = 0;
for (int i = 1; i <= n; i ++){
res = max(res, f[i]);
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/506026.html
標籤：其他