06 最長上升子序列 LIS

 1 /*
 2     給定一個無序的整數數組，找到其中最長上升子序列的長度。
 3     子序列是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。
 4     例如，[3,6,2,7] 是數組 [0,3,1,6,2,2,7] 的一個子序列。
 5 
 6     
 7 */
 8 
 9 #include <iostream>
10 #include <vector>
11 #include <algorithm>
12 using namespace std;
13 
14 int lengthOfLIS(vector<int>& nums) {
15     if (nums.empty()) return 0;
16     int n = nums.size();
17     vector<int> dp(n, 1);
18     int ans = 1;
19     for (int i = 1; i < n; ++i) {
20         for (int j = 0; j < i; ++j) {
21             if (nums[j] < nums[i]) {
22                 /*
23                      如果條件滿足，說明又找到一個可以增加長度的數字nums[j]，那么原有dp[j]會再增加一個長度，
24                      但nums[i]和比num[j]前面的數字num[0]~num[j-1]進行比較時，如果也有條件滿足的數字，
25                      dp[i]也會加長度的，所以dp[i]里面也是有長度記載的，此時需要比較當次再增加一個長度
26                      的 dp[j] + 1 和 dp[i] 哪個大才是目前最大的長度
27                 */
28                 dp[i] = max(dp[i], dp[j] + 1);    
29             }
30         }
31         ans = max(ans, dp[i]);
32     }
33     return ans;
34 }
35 
36 int main() {
37     vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
38     cout << "最長上升子序列的長度為: " << lengthOfLIS(nums) << endl;
39     return 0;
40 }
41 
42 
43 
44 /*
45     思路
46     定義 dp[i] 表示以第 i 個元素結尾的最長上升子序列的長度。
47     狀態轉移方程為：dp[i] = max(dp[j]) + 1，其中 0 <= j < i 且 nums[j] < nums[i]。
48 */