方法一：動態(tài)規(guī)劃

• dp[i]：末尾元素為arr[i]的最長子序列的長度

從0遍歷到i - 1，若遍歷到的元素小于當(dāng)前值arr[i]，表示當(dāng)前值arr[i]可以和前面的某個值組成遞增序列，則嘗試更新dp[i]

int LIS(vector<int>& arr) {int n = arr.size();if(n == 0) return 0;vector<int> dp(n, 1);int ans = 1;for(int i = 1; i < n; i++){for(int j = 0; j < i; j++){if(arr[j] < arr[i]){dp[i] = max(dp[i], dp[j] + 1);}}ans = max(ans, dp[i]);}return ans;
}

時間復(fù)雜度：$O(N^2)$

方法二：貪心 + 二分查找

我們考慮維護(hù)一個數(shù)組 min_tails，min_tails[i]表示長度為i + 1的遞增子序列末尾元素的最小值，min_tails并不是記錄arr中的遞增子序列

看最后一個g數(shù)組，g[2]=3，表示長度為3的遞增子序列末尾的最小值為3。長度為3的遞增子序列有[1,6,7]、[1,2,4]、[1,2,5]、[1,2,3]

為什么min_tails數(shù)組中要維護(hù)各個不同長度遞增子序列末尾元素的最小值呢？

min_tails數(shù)組中維護(hù)各個不同長度遞增子序列末尾元素的最小值時，arr的后續(xù)元素可以和不同長度子序列末尾的最小值比較，從而確定后續(xù)元素可以加入哪個子序列，成為新的遞增子序列

int LIS(vector<int>& arr) {int n = arr.size();if(n == 0) return 0;vector<int> tails(n);min_tails[0] = arr[0];int len = 1;for(int i = 1; i < n; i++){// 如果當(dāng)前元素比長度為len的子序列末尾元素的最小值大，說明當(dāng)前元素可以和長度為len的子序列組成新的遞增子序列if(min_tails[len - 1] < arr[i]){min_tails[len] = arr[i];len++;continue;}// 二分：用arr[i]更新tails中最靠左側(cè)的大于arr[i]的值int l = 0;int r = len;while(l < r){int mid = l + (r - l) / 2;if(min_tails[mid] < arr[i]) l = mid + 1;  // 用l找第一個比arr[i]大的值，也可以找最后一個小于等于arr[i]的值else r = mid;}min_tails[l] = arr[i];}return len;
}

構(gòu)造最長遞增子序列

max_len相同時取最小的，ans初始化為len個元素，從后往前填寫。如果max_len相同，靠后的arr[i]一定更小，若靠后的arr[i]更大，那max_len就不能相同了。比如：

class Solution {
public:vector<int> LIS(vector<int>& arr) {int n = arr.size();if(n < 2) return arr;vector<int> min_tails(n); // min_tails[i]：長度為i+1的最長遞增子序列末尾元素的最小值min_tails[0] = arr[0];int len  = 1;             // 當(dāng)前最長遞增子序列的長度vector<int> max_len(n);   // max_len[i]：表示以arr[i]結(jié)尾的最長遞增子序列的長度max_len[0] = 1;for(int i = 1; i < n; i++){// 當(dāng)前元素arr[i]已經(jīng)比當(dāng)前最長遞增子序列末尾元素的最小值要大，說明可以和當(dāng)前遞增子序列組成新的遞增子序列if(arr[i] > min_tails[len - 1]){min_tails[len] = arr[i];max_len[i] = len + 1; // arr[i]可以增加最長遞增子序列的長度len++;continue;}// arr[i]不能和當(dāng)前最長遞增子序列組成新的遞增子序列，可以嘗試用arr[i]和較短的遞增子序列組成新的遞增子序列（極端情況下，arr[i]自己組成長度為1的遞增子序列）// 在[l, r)之間找第一個大于arr[i]的位置，說明arr[i]可以和前面較短的遞增子序列組成新的遞增子序列，用arr[i]更新第一個大于arr[i]的元素，即讓某遞增子序列的長度不變，而末尾元素變小int l = 0;int r = len;while(l < r){int mid = l + (r - l) / 2;if(min_tails[mid] < arr[i]) l = mid + 1;else r = mid;  // 不能是r = mid - 1，因為要找第一個大于arr[i]的值，此時min_tails[mid] >= arr[i]，r = mid - 1會跳過大于arr[i]的min_tails[mid]}min_tails[l] = arr[i];max_len[i] = l + 1;  // arr[i]不能增加最長遞增子序列的長度，min_tails[l]是第一個大于arr[i]的元素，即用arr[i]可以組成長度為l + 1的遞增子序列}vector<int> ans(len);int idx = len - 1;// 只能按順序填for(int i = n - 1; i >= 0; i--){// 遍歷max_len數(shù)組，最大長度為idx + 1時才可填寫ans[idx]，max_len相同時必然取最靠后的arr[i]，因為最靠后的最小if(max_len[i] == idx + 1){ans[idx] = arr[i];idx--;}}return ans;}
};