题目描述

设有由 $n$ 个 (可能有相同) 的整数组成的数列，记为: {$a_1$、$a_2$、...、$a_n$} 。

例如 {3，18，7，14，10，12，23，41，16，24}。若存在 $i_1 \lt i_2 \lt i_3 \lt \dots \lt i_e$ 且有 $a_{i_1} \le a_{i_2} \le ... \le a_{i_e}$ 则称为长度为 $e$ 的不下降子序列。

如上例中 {3，18，23，24} 就是一个长度为 $4$ 的上升序列，同时也是 {3，7，10，12，16，24} 长度为 $6$ 的不下降子序列。

程序要求，当原数列给出之后，求出最长的不下降子序列的长度。

输入格式

第一行为 $n$，表示 $n$ 个数（$10 \le n \le 100000$）

第二行 $n$ 个整数，数值之间用一个空格分隔（$-10^9 \le a_i \le 10^9$）

输出格式

一个整数，代表最长不下降子序列的长度。

数据样例

3
1 2 3

3

7
1 3 7 7 11 8 10

5

题目分析

假设您已经学过了基于动态规划算法求最长上升子序列，在那个算法中，我们用一个 dp[] 数组记录每一个 $_i$ 为序列最后一个数字的情况下的最长上升子序列长度。然后递推 dp[i] 的时候，状态转移方程式：

$dp[i] = max_{j=1}^{j<i}(dp[j]+1)$ ，通过要求每一个 $a_j \le a_i$

for(int i=1;i<=n;i++){
	dp[i] = 1;
	for(int j=1; j<i ;j++){
		if(a[j]<=a[i])
			dp[i] = max(dp[i], dp[j]+1)
	}
	ans = max(ans, dp[i]);
}

这个算法的时间复杂度为 O($n^2$)，而本题的 $n$ 最大可能到 $10^5$，因此，O($n^2$) 就一定超时了。

又假设你已经学过基于二分查找算法优化最长上升序列，那么完全可以基于这个算法简单修改之后应用到本题。类似地，我们引入一个数组 $x[i]$ 用于记录长度为 $i$ 的最长不下降序列的最后一个数字最小是什么。

1. 假如 $a_i \le x_{len}$ 那意味着 $a_i$ 可以放在长度为 $len$ 的不下降子序列后面，延伸出一个长度为 $len+1$ 的不下降子序列。

2. 否则，找到第一个 $x_j \gt a_i$，==这次就不需要再看 $x_{j-1}$ 是否小于 $a_i$ 了，小于也行，等于也行，$a_i$ 都可以放在长度为 $j-1$ 的不下降序列后面，构造出一个新的长度为 $j$ 的不下降序列 {$...,x_{j-1},a_i$}

3. 因此，$x_j$ 是一个不下降序列，里面有可能有 $x_i == x_{i-1}$，我们要维护好这个 $x[]$ 序列。

4. 这个算法的时间复杂度为 O($n \log_2 n$)

完善程序

#include<bits/stdc++.h>
using namespace std;
int n,x[100001],len;

int main()
{
	scanf("%d",&n);

	int a; // a[i] 只用一次，不需要持久化到数组
	int *pt; // int 指针变量

	for(int i=1;i<=n;i++){
		scanf("%d",&a);

		if(len==0|| __填空(1)__)
			__填空(2)__; // 新来的 a 可以放在长度为 len 的上升序列后面，构造出一个长度为 len+1 的上升序列
		else{
			pt = __填空(3)__;
			__填空(4)__；
		}
	}
	cout<<len;
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}