python/TangDou/AcWing/LIS/895.md

##AcWing 895. 最长上升子序列

一、题目描述

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

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

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

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

数据范围 1≤N≤1000，−10^9≤数列中的数≤10^9

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

二、动态规划

状态表示 f[i]表示从第一个数字开始算，以a[i]结尾的最长的上升序列长度。(以a[i]结尾的所有上升序列中属性为最长的那一个)

状态计算

\large  \left\{\begin{array}{l}
f[i] =1  &  默认值，前面没有比i小的，以a[i]结尾的最长个数是1 \\
f[i] = max(f[i], f[j] + 1) & 0 \le j<i \ \& \  a[j]<a[i] 
\end{array}\right.

时间复杂度 O(n^2)

三、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n;
int a[N], f[N];
int res;

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

    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    printf("%d", res);
    return 0;
}

四、输出路径

/*
测试用例：
7
3 1 2 1 8 5 6

答案：
4
1 2 5 6
*/

额外记录的信息

• pos:记录最大LIS值出现时的数组下标pos,它是最大值的起始位置，一会要倒序从它开始，一直到1，通过递推前序的办法不断的向前倒序查找来源路径。

• pre[i]:原始数组的每一个数字，都配套一个pre[i],它和f[i]是成对出现的

  • f[i]:表示从第一个数字开始算，以w[i]结尾的最长的上升序列长度
  • pre[i]:它能获取到的f[i]这个最大长度时，是从哪个前序位置转移而来，也就是借了谁的光，依赖于谁过来的。
  • 边界：最左侧第1个没有借任何人的光，初始默认值是0,这也是递归的终止条件。

输出路径代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;

int n, a[N];
int f[N];
int res, pos; // LIS最大长度  pos:最大长度是哪个下标数字提供
int pre[N];   // 记录转移的前序关系

// ① 循环+vector打印路径
void print(int k) {
    vector<int> path; // 因为查找的关系是逆序的，需要用一个向量数组把这个逆序反过来，才能输出
    while (k) {
        path.push_back(a[k]);
        k = pre[k];
    }
    // 倒序输出LIS序列
    for (int i = path.size() - 1; i >= 0; i--) printf("%d ", path[i]);
}

// ② 递归打印路径
void out(int k) {
    if (pre[k]) out(pre[k]); // 因为最前面的第1号，它的前序
    printf("%d ", a[k]);
}

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

    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[i] > a[j] && f[i] <= f[j]) {
                f[i] = f[j] + 1;
                pre[i] = j; // f[i]的前序是f[j]
            }

        // 更新最大值
        if (f[i] > res) {
            res = f[i]; // 记录LIS最大值
            pos = i;    // 记录LIS最大值时相应的数组下标i
        }
    }

    // 输出LIS最大长度
    printf("%d\n", res);

    // 循环
    print(pos);

    puts("");
    // 递归
    out(pos);

    return 0;
}