题目描述

设有由 n 个不相同的非负整数组成的数列，记为：b(1)、b(2)、……、b(n) 且 b(i)≠b(j)（i≠j)，若存在 i1 ＜ i2 ＜ i3 ＜ … ＜ ie 且有 b(i1) ＜ b(i2) ＜ … ＜ b(ie) ，则称为长度为 e 的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。

例如：13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中 13，16，18，19，21，22，63 就是一个长度为 7 的不下降序列，同时也有 7 ，9，16，18，19，21，22，63 长度为 8 的不下降序列。

输入格式

第一行为一个正整数 n 。

第二行为 n 个非负整数序列，每个数不超过 10000 。

输出格式

输出一个正整数，为最长的不下降序列的长度。

输入输出样例

输入

14 13 7 9 16 38 24 37 18 4 19 21 22 63 15

输出

8

说明/提示

【数据范围】

对于 30% 的数据，n≤1000；

对于 100% 的数据，n≤5000；

求问这个代码的原理：

#include<bits/stdc++.h>
using namespace std;

int n,a,tail=0,mid,dp[100009];

int main()
{
	dp[0]=0;
	int tail=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		int low=0,high=tail-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(dp[mid]>=a) high=mid-1;
			else low=mid+1;
		 } 
		 if(low>=tail) tail++;
		 dp[low]=a;
	}
	printf("%d\n",tail);
	return 0;
}

感激不尽QWQ