POJ3903 Stock Exchange
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1e5+;
int a[maxn];
int main() {
int n;
while (~scanf("%d",&n)) {
for (int i = ; i <= n; ++i) scanf("%d",&a[i]);
vector<int> ve;
ve.push_back(a[]);
for (int i = ; i <= n; ++i) {
if (ve[ve.size()-] < a[i]) {
// 如果新进来的数比最后一个数大,那么直接插入
ve.push_back(a[i]);
}
else {
ve[lower_bound(ve.begin(),ve.end(),a[i])-ve.begin()] = a[i];
}
}
printf("%d\n",ve.size());
}
return ;
}