题目描述

给定一个无需的整数数组，找出其最终最是长上升子序列的长度

输入

5 7 1 9 4 6 2 8 3

输出

4

即 1，4，6，8

思路

在进行动态规划时，我们要注意递推公式的无后效性，所以我们考察上升子序列时以 i 处的数字作为序列结尾，这样结果并不依赖于后续元素，便于我们寻找递推关系

一维线性的递推，考虑以一位数组 f[i] 作为递推数组，记录以a[i]为结尾的最长上升子序列长度

初始化条件 f[i] = 1

递推式
$$
如果 a[i]>a[j] \ and \ f[j]+1>f[i] \
f[i] = f[j] + 1 \ \ 1<=j<i
$$
这里的时间复杂度为$O(n^2)$

给出代码（状态转移方程）

if (a[j] > a[i])
    f[i] = max(f[i], f[j] + 1);

题解模板

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

int n;
int a[5005], f[5005], ans = 0;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++)
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
        ans = max(ans, f[i]);
    }
    cout << ans;
    return 0;
}

优化思路

这里我们发现每次第二层的 f[j] 循环的有效部分均为 f[j] 的最大值，因此我们可以尝试使用二分来优化算法

二分查找的前提是有序，因此我们增加一个 b 数组来记录上升子序列

len = 1;
b[1] = a[1];
// 动态更新b数组
for(int i = 2; i <= n; i++) {
    if(a[i] > b[len])
        b[++len] = a[i];
    else{
        j = find(a[i]);
        b[j] = a[i];
    }
}

考虑新增一个元素 a[i]

1. 大则添加：如果 a[i] 大于 b[len]，直接让 b[++len] = a[i]。即 b 数组的长度增加 1，且添加了一个元素
2. 小则替换 ：如果 a[i] 小于等于 b[len]，用 a[i] 替换掉 b 数组中第一个大于或等于 a[i] 的元素。假设第一个大于 a[i] 的元素是 b[j]，那么 a[i] 替换掉 b[j] 后，会使得 b[1…j]这个上升子序列的结尾元素更小。对于一个上升子序列，其结尾元素越小，越有利于续接其他元素

最后 b 数组的长度 len 就是最长子序列长度

实现代码

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

int n;
int a[5005], b[5005], len = 1;
int find(int x) {
    int l = 1, r = len;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (b[mid] < x)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return l;
}

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

    b[1] = a[1];
    for (int i = 2; i <= n; i++) {
        if (a[i] > b[len])
            b[++len] = a[i];
        else {
            int j = find(a[i]);
            b[j] = a[i];
        }
    }
    cout << len;
    return 0;
}

复杂度$O(\log n)$

比起动态规划更接近贪心的思想