AcWing 896. 最长上升子序列 II

题目

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式 第一行包含整数 $N$。

第二行包含 $N$ 个整数，表示完整序列。

输出格式 输出一个整数，表示最大长度。

数据范围 $1≤N≤100000，−10^9≤数列中的数≤10^9$ 输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

思路

状态表示 -- 集合：从前i个物品选，形成递增子序列的长度的集合
         -- 属性：长度
状态计算：
    当遍历到第i个物品时，子序列可能是1~i-1中的传递过来
    从1跳到i: f[i] = f[1] + 1
    从2跳到i: f[i] = f[2] + 1
    ...
    从i-1跳到i: f[i] = f[i - 1] + 1
由以上可知核心公式为：f[i] = max(f[1] + 1, f[2] + 1, ..., f[i - 1] + 1)

================
优化：
当遍历到i时，从1 ~ i - 1中选一个结尾值较大的明显可以使得子序列长度更长。

y: 子序列末尾值
 ^
 |        |
 |    |   |
 | |  |   |
-------------> x: 子序列长度
我们假定随着子序列长度增加，子序列末尾值是递增的，由反证法：
    假如 y[1] > y[2]，则序列2必然可以形成以序列1末尾值结尾的更满足的序列。
因此我们可以通过二分法来找到一个小于i的最大值。

代码

#include <iostream>

using namespace std;

const int N = 100010;

int q[N];
int a[N];

int main()
{
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    
    int len = 0;
    for (int i = 1; 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;
}