思路
对于长度为 1 的上升子序列,我们可以发现 1 比 3 更好,因为可以接在 3 后面的序列一定可以接在 1 后面,同时,能够接在 1 后面的序列不一定能接在 3 后面,如果有相同的就去第一次出现的(比如这里有两个 1,那对于长度为 1 的子序列我们就选取第一个 1)。综上,对于各长度的子序列中,存储其最后一个数最小的序列。
我们最后存储下的数组应该是单调递增的。反证法:假设长度为 6 的子序列最后一个值小于等于长度为 5 的子序列最后一个值,那么长度为 5 的子序列就不应该存储它本身,应该存储长度为 6 的子序列的前五个数字构成的序列。这样就和我们对于该数组的定义(对于各长度的子序列中,存储其最后一个数最小的序列)矛盾了,因此假设不成立。
有了这个数组 q[N] 以后,我们如果想求以 ai 结尾的最大上升子序列,我们可以先找见 q 中小于 ai 最大的那个子序列,ai 加在其后就是答案了。
那如何在这个有序序列中找到小于 ai 的最大的数呢?通过二分来查找。
解释 len = max(len, r + 1);
这一步的目的是确保在每次迭代中,len
变量都记录着当前最长递增子序列的长度。在每次迭代中,我们通过二分查找找到了当前元素 a[i]
应该插入的位置 r
,然后将 len
更新为当前值和 r + 1
的最大值。
考虑以下情况:
- 如果
r + 1
大于当前的len
,说明我们在a[i]
插入后得到了一个更长的递增子序列,因此我们需要更新len
。 - 如果
r + 1
小于或等于当前的len
,则说明我们找到的位置r
没有带来更长的递增子序列,因此不需要更新len
。
通过这种方式,我们始终保持 len
记录着当前的最长递增子序列的长度,而不会错过任何可能的更新。
解释 q[0] = -2e9;
这一步是为了确保在二分查找过程中,如果当前元素 a[i]
比所有已知的 LIS 元素都要小,它能够被正确地插入到 LIS 的开头位置。
具体来说,将 q[0]
初始化为一个非常小的值(这里是 -2e9
)是为了确保在二分查找的过程中,当 a[i]
比当前 LIS 中所有元素都小时,它可以被插入到 LIS 的开头。
考虑这种情况:如果 q[0]
不是一个非常小的值,而是序列中的某个实际元素,那么当 a[i]
比所有 LIS 中的元素都小时,二分查找将无法找到比 a[i]
更小的位置,因为它将在数组的开头就被插入。
通过将 q[0]
初始化为一个极小的值,我们确保在二分查找时,当 a[i]
小于所有 LIS 元素时,它能够被插入到数组的开头位置(即 q[0]
的位置),从而保证了算法的正确性。
代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N], q[N];
int main()
{
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
int len = 0;
q[0] = -2e9;
for(int i = 0; i < n; i ++)
{
int l = 0, r = len;
while(l < r)
{
int mid = l + r + 1 >> 1; // 向上取整
if(q[mid] < a[i]) l = mid;
else r = mid - 1;
}
len = max(len, r + 1);
q[r + 1] = a[i];
}
cout << len << endl;
return 0;
}