题目链接：最长上升子序列 II

整个数组长度更大，以$O(N^2)$时间复杂度运行会超时

对于最长上升子序列1的题目，求解以第$i$个数结尾的最长升子序列的结果时，需要从前向后依次对比第$0\sim i-1$个已有结果，其目的是找到$0\sim i-1$范围内的上升序列且序列的最后一个元素小于$a[i]$。如果这些序列中最长的是以第$j(0\leq j\leq i-1)$个元素结尾，则此时$f(i)=f(j)+1$

若$0\sim i-1$范围内最长的上升序列的长度为$len$，则该范围内是可能有多个满足以上条件的序列，使得$f(i)=f(j)+1$的。在这么多满足条件的序列中，我们可以选出最后一个元素值最小的，作为长度为$len $的最长上升子序列的代表，这样可以保证后续有最多的$a[i]$可以满足比长度为$len $的最长上升子序列的最后一个元素大，以求得$f(i)$可能的最大值。

因此，在$0\sim i-1$范围内我们只需要记录不同长度（$0\sim len$）最长上升子序列代表的最后一个元素，当求解$f(i)$时，只需要拿$a[i]$与不同长度最长上升子序列代表的最后一个元素做对比，找到尽可能长且最后一个元素比$a[i]$小的最长上升子序列代表，记其最后一个元素的索引为$j$，则此时$f[i]=f[j]+1$

若$0\sim i-1$范围内最长上升子序列的长度为$len$，则长度为$len$的最长上升子序列代表，其最后一个元素值一定大于长度为$len-1$的最长上升子序列代表最后一个元素的值，这是因为：

• 长度为$len-1$的最长上升子序列代表，（根据上面的定义）其最后一个元素是所有长度为$len-1$上升子序列的最小值
• 对于长度为$len$的最长上升子序列代表，其最后一个元素一定大于倒数第二个元素。且其前$len-1$个元素可以构成长度为$len-1$的上升子序列，结合上升子序列代表的定义，该上升子序列最后一个元素的值一定$\geq$长度为$len$的最长上升子序列代表最后一个元素的值
• 因此，对于长度分别为$0\sim len$的最长上升子序列代表，它们的最后一个元素值是依次递增的。这使得求解以$a[i]$结尾的最长上升子序列时，可以使用二分查找找到尽可能长且最后一个元素比$a[i]$小的最长上升子序列代表。

根据以上分析，求解以$a[i](i\in[0,n])$结尾的最长上升子序列的代表时：

1. 使用数组$q[idx]$保存长度为$idx$的最长上升子序列代表最后一个元素的值
2. 使用$len$记录$0\sim i-1$中存在的最长上升子序列的长度
3. 在$q$的$[0,len]$范围内，通过二分查找，找到尽可能长且最后一个元素比$a[i]$小的最长上升子序列代表，记其长度为$r$
4. 此时$0\sim i$范围内：
   • 最长的上升子序列长度$len=\max{\{len, r+1\}}$
   • 由于此时$q$数组中，长度为$r$最长上升子序列代表最后一个元素小于$a[i]$，且长度为$r+1$最长上升子序列代表最后一个元素大于$a[i]$。而长度为$r$最长上升子序列代表和$a[i]$构成的长度为$r+1$的最长上升子序列，其最后一个元素的值小于当前$q$中长度为$r+1$最长上升子序列代表最后一个元素。因此应该置$q[r+1]=a[i]$

以上流程构成了$O(n\log n)$复杂度的求解方法，代码为：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int a[N];  // 保存整数序列
int q[N];  // 第 idx 个元素记录长度为 idx 的最长上升子序列代表最后一个元素值

int n;  // 序列中元素个数

int main() {

  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  int len = 0;  // 记录 0~i 中最长上升子序列的长度

  q[0] = -2e9;  // 作为二分查找的边界，保证至少可以找到一个长度为 0 的最长上升子序列代表
  for (int i = 0; i < n; ++i) {
    // 在 q 的 0~len 区间查找尽可能长，且最后一个元素比 a[i] 小的最长上升子序列代表
    int l = 0, r = len;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      // 查找比 a[i] 小的第一个元素
      if (q[mid] < a[i]) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }

    len = max(len, r + 1);
    q[r + 1] = a[i];
  }

  cout << len;
  return 0;
}