給定一個數組，求最長遞增子序列的長度,就是要求我們求出一個序列中最長的上升子序列的長度，最長上升子序列的定義就是從原序列中按照孫旭去除一些數字，這些數字是逐漸增大的。
*定義dp[i]表示以第i個元素結尾的最長上升子序列的長度。
*初始時，每個dp[i]的值至少為1，因為每個元素本身就是一個長度為1的上升子序列
*對于每個元素i，我們遍歷起前面的所有元素j，如果nums[i] < nums[j]，則更新
dp[i] = max(dp[i],dp[j] + 1)。
*最終，最長上升子序列的長度就是dp數組中的最大值。
函數邏輯
-
輸入與邊界處理：
-
輸入為整數向量?
nums。 -
若數組為空（
n == 0），直接返回 0。
-
-
動態規劃初始化：
-
創建長度為?
n?的數組?dp，初始值全為 1。dp[i]?表示以?nums[i]?結尾的最長遞增子序列的長度（每個元素自身至少構成長度為 1 的子序列）。
-
-
動態規劃遞推：
-
外層循環遍歷每個元素?
nums[i]（從第 2 個元素開始）。 -
內層循環遍歷?
nums[i]?之前的所有元素?nums[j]（j < i）。 -
若?
nums[j] < nums[i]，說明可以將?nums[i]?接在?nums[j]?對應的遞增子序列后。此時更新?dp[i]?為?max(dp[i], dp[j] + 1)，確保?dp[i]?記錄當前最長長度。
-
-
返回結果：
-
最終返回?
dp?數組中的最大值，即整個數組的最長遞增子序列長度。
-
示例驗證
以輸入?[10, 9, 2, 5, 3, 7, 101, 18]?為例：
-
dp?數組逐步更新為?[1, 1, 1, 2, 2, 3, 4, 4]。 -
最大值為 4，對應最長遞增子序列如?
[2, 5, 7, 101]。
復雜度分析
-
時間復雜度：O(n2)，兩層嵌套循環遍歷所有元素對。
-
空間復雜度：O(n)，用于存儲?
dp?數組。
#include <iostream>
#include <vector>
#include <algorithm> // 用于max_elementusing namespace std;/*** 使用動態規劃求最長遞增子序列長度* @param nums 輸入數組* @return 最長遞增子序列的長度*/
int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 0) return 0;// dp[i]表示以nums[i]結尾的最長遞增子序列的長度vector<int> dp(n, 1); // 初始化為1，每個元素自身就是一個子序列for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) {// 如果nums[j] < nums[i]，則可以擴展子序列dp[i] = max(dp[i], dp[j] + 1);}}}// 返回dp數組中的最大值return *max_element(dp.begin(), dp.end());
}/*** 輸出最長遞增子序列本身（而不僅僅是長度）* @param nums 輸入數組* @return 最長遞增子序列*/
vector<int> getLIS(vector<int>& nums) {int n = nums.size();if (n == 0) return {};vector<int> dp(n, 1);vector<int> prev(n, -1); // 用于記錄前驅元素索引for (int i = 1; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {dp[i] = dp[j] + 1;prev[i] = j; // 記錄前驅}}}// 找到dp數組中最大值的索引int max_len = 0, max_index = 0;for (int i = 0; i < n; ++i) {if (dp[i] > max_len) {max_len = dp[i];max_index = i;}}// 回溯構建LISvector<int> lis;while (max_index != -1) {lis.push_back(nums[max_index]);max_index = prev[max_index];}reverse(lis.begin(), lis.end()); // 反轉得到正確順序return lis;
}int main() {vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};// 計算并輸出最長遞增子序列長度int length = lengthOfLIS(nums);cout << "最長遞增子序列長度: " << length << endl;// 獲取并輸出最長遞增子序列本身vector<int> lis = getLIS(nums);cout << "最長遞增子序列: ";for (int num : lis) {cout << num << " ";}cout << endl;return 0;
}
