Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int CeilIndex(std::vector<int>& v, int l, int r, int key)
- {
- while (r - l > 1) {
- int m = l + (r - l) / 2;
- if (v[m] >= key)
- r = m;
- else
- l = m;
- }
- return r;
- }
- int LongestIncreasingSubsequenceLength(std::vector<int>& v)
- {
- if (v.size() == 0)
- return 0;
- std::vector<int> tail(v.size(), 0);
- int length = 1;
- tail[0] = v[0];
- for (size_t i = 1; i < v.size(); i++) {
- if (v[i] < tail[0])
- tail[0] = v[i];
- else if (v[i] > tail[length - 1])
- tail[length++] = v[i];
- else
- tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i];
- }
- return v.size()-length;
- }
- int main()
- {
- int a,n,b;
- vector<int> v;
- cin>>a;
- for(int i=0;i<a;i++)
- {
- cin>>n;
- for(int j=0;j<n;j++)
- {
- cin>>b;
- v.push_back(b);
- }
- cout<<LongestIncreasingSubsequenceLength(v)<<endl;
- v.clear();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement