思路:使用一个栈来求最长上升子序列的长度,当栈为空或者待插入元素大于栈顶元素时就入栈,否则替换栈中小于等于待插入元素的数并替换,最终栈的长度即为最长上升子序列的长度.
优点:使用二分查找,时间复杂度为O(nlogn).

#include<iostream>#include<vector>using namespace std;vector<int> v;int solution(int arr[], int length){ for(int i = 0; i < length; i++) { if(v.size() == 0 || arr[i] > v[v.size() - 1]) //如果栈空或者大于栈顶就入栈 v.push_back(arr[i]); else //查找栈中小于等于arr[i]的元素并替换 { int begin = 0, end = v.size() - 1; int index = -1; while(begin <= end) { int mid = (end - begin) / 2 + begin; if(arr[mid] < arr[i]) begin = mid + 1; else { index = mid; end = mid - 1; } } v[index] = arr[i]; } }}int main(){ int arr[] = {1,-1,2,-3,4,-5,6,-7}; int res = solution(arr,8); for(int i = 0; i < v.size(); i++) cout<<v[i]<<" "; cout<<endl; cout<<v.size()<<" "; return 0;}

运行结果: