class Solution { public: /** * retrun the longest increasing subsequence * @param arr int整型vector the array * @return int整型vector */ int biSearch(int x, vector<int>& dp) { int left = 0, right = dp.size() - 1, mid; while(left < right) { mid = (left + right) / 2; if(dp[mid] < x) left = mid + 1; else right = mid; } return left; } vector<int> LIS(vector<int>& arr) { // write code here if(arr.size() == 0) { vector<int> res; return res; } vector<int> len; //设置数组长度大小的动态规划辅助数组 vector<int> dp; //用于二分划分的辅助数组 dp.push_back(arr[0]); // 初始化 len.push_back(1); for(int i = 1; i < arr.size(); i++) { if(arr[i] > dp[dp.size() - 1]) { dp.push_back(arr[i]); len.push_back(dp.size()); } else { int t = biSearch(arr[i], dp); // t为att[i]在dp数组中的索引 dp[t] = arr[i]; // 如果没有找到arr[i],更新dp中的数值,将arr[i]压入dp len.push_back(t + 1); // 存储arr[i]对应的递增自序列的长度 } } int j = dp.size(); // j == 最长递增子序列的长度 vector<int> res(j); for(int i = len.size() - 1; j > 0; i--) { // 逆向找 if(len[i] == j) { j--; res[j] = arr[i]; } } return res; } };