1 int binSearch(const vector<int> &tail, int len, int key)// 2 { 3     int left = 0, right = len - 1; 4     int mid; 5  6     while(left <= right) 7     { 8         mid = left + ((right - left) >> 1); 9         if(tail[mid] == key)10             return mid;11         else if(tail[mid] > key)12             right = mid - 1;13         else14             left = mid + 1;15     }16 17     return left;//18 }19 20 void LIS(int *a, int n)21 {22     vector<int> tail(n); //当前子序列的结尾，递增的23     vector<int> orig(n); //当前结尾在原始数组的下标24     vector<int> prev(n); //当前结尾的上一元素下标25     int len = 0;26 27     tail[0] = a[0];//28     orig[0] = 0;29     prev[0] = -1;30     ++len;31 32     for(int i = 1; i < n; ++i)33     {34         if(a[i] > tail[len - 1])//35         {36             tail[len] = a[i];//37             orig[len] = i;38             prev[i]   = orig[len - 1];39                         40             ++len;41         }42         else43         {44             int pos = binSearch(tail, len, a[i]);45             tail[pos] = a[i];//46             orig[pos] = i;47             prev[i]   = pos > 0 ? orig[pos - 1] : -1;48         }49     }50 51     stack<int> stk;//52     for(int cur = orig[len - 1]; cur >= 0; cur = prev[cur])53     {54         stk.push(a[cur]);55     }56 57     cout << len << endl;58     while(!stk.empty())59     {60         cout << stk.top() << ‘ ‘;61         stk.pop();62     }63     cout << endl;64 }