python/TangDou/AcWing/LIS/895.md

##[$AcWing$ $895$. 最长上升子序列 ](https://www.acwing.com/problem/content/description/897/)

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

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

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

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

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

**输入样例**：
```cpp {.line-numbers}
7
3 1 2 1 8 5 6
```

**输出样例**：
```cpp {.line-numbers}
4
```


### 二、动态规划

**状态表示** 
$f[i]$表示从第一个数字开始算，以$a[i]$<font color='red'><b>结尾</b></font>的最长的上升序列长度。(以$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)$ 

### 三、实现代码
```cpp {.line-numbers}
#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;
}
```

### 四、输出路径
```c++
/*
测试用例：
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]$<font color='red'>结尾</font>的最长的上升序列长度
  * $pre[i]$:它能获取到的$f[i]$这个最大长度时，是从哪个前序位置转移而来，也就是借了谁的光，依赖于谁过来的。
  * **边界**：最左侧第$1$个没有借任何人的光，初始默认值是$0$,这也是递归的终止条件。

#### 输出路径代码
```cpp {.line-numbers}
#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;
}

```