动态规划--最长上升子序列最大长度 时间复杂度优化

单调队列的维护

#include<bits/stdc++.h>
using namespace std;
int t,n,dp[1005],x,cnt;
int f(int val,int l,int r){int ans;while(l<=r){int mid = (l+r)>>1;if(dp[mid] > val){ans = mid;r = mid-1;}else if(dp[mid] == val) return -1;else l = mid + 1;}return ans;
}
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);cnt = -1;for(int i = 0;i<n;i++){scanf("%d",&x);if(i == 0 || x > dp[cnt]) dp[++cnt] = x;else{int p = f(x,0,cnt);if(p == -1) continue;else dp[p] = x;}  }printf("%d\n",cnt+1);}
}