#include <iostream>
int n, cnt;
using namespace std;
int a[1200], dp[1200];
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
dp[cnt++] = a[0];
for (int i = 1; i < n; i++) {
int la = 0, r = cnt, v = a[i];
if (v > dp[cnt-1]) dp[cnt++] = v;
else {
while (la < r - 1) {
int m = la + r >> 1;
if (dp[m] >= v) r =m;
else la = m;
}
if (dp[la] >= v) r = la;
dp[r] = v;
}
}
//for (int i = 0; i < n+1; i++) cout << dp[i] << ' ';
cout << cnt << endl;
return 0;
}
平时写的二分是找小于或者等于v的第一个数,
这次找大于v的第一个数,加一句if (dp[la] >= v) r = la; 就可以
因为整数除法的特性,这里赋值dp[r] = v; 而没有这一句的话,r的取值范围是(la +1 到 N);