2085.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2085 on 2005-12-26 at 19:16:08 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 10240;

int main()
{
	int n, i;
	int up[MAX], down[MAX], left[MAX], right[MAX];
	int lup[MAX], rup[MAX], lun, run;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) {
			int a;
			scanf("%d", &a);
			up[i] = down[n-1-i] = a;
		}
		lun = run = 0;
		for(i = 0; i < n; i++) {
			left[i] = lower_bound(lup, lup+lun, up[i]) - lup;
			lup[left[i]] = up[i];
			if(left[i] == lun) lun++;
			right[n-1-i] = lower_bound(rup, rup+run, down[i]) - rup;
			rup[right[n-1-i]] = down[i];
			if(right[n-1-i] == run) run++;
		}
		int best = 0;
		for(i = 0; i < n; i++) best = max(best, 2*min(left[i], right[i])+1);
		printf("%d\n", best);
	}
	
	return 0;
}