最长上升子序列
View Code #include#include #include #include #include using namespace std;#define maxn 100005int n;int top;int stk[maxn];int binarysearch(int l, int r, int a){ if (l > r) return l; if (a > stk[r]) return r + 1; while (l < r) { int mid = (l + r) / 2; if (stk[mid] < a) l = mid + 1; else r = mid; } return l;}int main(){ //freopen("t.txt", "r", stdin); while (scanf("%d", &n) != EOF) { top = 0; for (int i = 0; i < n; i++) { int a; scanf("%d", &a); int index = binarysearch(0, top - 1, a); stk[index] = a; top = max(top, index + 1); } printf("%d\n", top); } return 0;}