#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>

const int MAX = 100007;
int a[MAX], d[MAX];

inline int read() {
	char ch;
	while ((ch = getchar()) < '0' || ch > '9');
	int x = ch - '0';
	while ((ch = getchar()) >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + ch - '0';
	}
	return x;
}

int upper_bound(int l, int r, int x) {
	int mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (x > d[mid]) {
			l = mid + 1;
		} else {
			r = mid;
		}
	}
	return l;
}

void write(int x) {
	if (!x) return;
	write(x / 10);
	putchar(x % 10 + '0');
}

int main() {
	int n;
	d[0] = INT_MIN;
	while (~scanf(" %d", &n)) {
		for (int i = 1; i <= n; ++i) {
			a[i] = read();
		}
		
		int maxLen = 0, ind;
		for (int i = 1; i <= n; ++i) {
			if (a[i] > d[maxLen]) d[++maxLen] = a[i];
			else {
				ind = upper_bound(1, maxLen, a[i]);
				//ind = std::upper_bound(d + 1, d + maxLen + 1, a[i]) - d;这里用STL的upper_bound为啥会错？我也不知道... 
				d[ind] = a[i];
			}
		}
		//printf("%d\n", maxLen);
		write(maxLen);
		putchar('\n');
	}
	return 0;
}
就是上面求ind得那句，当然我并不了解STL中upper_bound的机制，在cplusplus.com中看了一下，对于STL自己封装的诸如vector好像没什么问题，就是不知道对普通的数组它会怎么处理？而且之前用从来没有遇到过问题。如果有谁知道，务必赐教！不胜感谢！

• Re:[附代码/求解/没过的请自行思考&别偷看]为何这里用STL的二分查找会出错?不解...求指点 (1378) wenfengmtd 2019-02-28 00:40:04