---
title: "最长上升子序列"
created: 2025-11-28
tags:
  - 算法
---

# 最长上升子序列

## 题目 [最长上升子序列](https://www.acwing.com/problem/content/897/)

![[image-73c224e9.png]]

## 思路分析

3 1 2 1 8 5 6中找到的最长上升子序列是 1 2 5 6 长度为4

可以用f[i]表示以a[i]结尾的上升子序列最大长度

有点类似于kmp算法 对于f[i]只需要找到它前面的比它小的一个数的f[j] 然后在它的基础上加1即可推到当前的f[i]

比如：f[7]表示以a[7]也就是6结尾的最长上升子序列的长度 那么它的状态就是从前面的 12 125……转移过来 长度就是2+1或3+1中更大的那一个

`for(int j=1;j<i;j++)`

`if(a[j]<a[i])`

`f[i]=max(f[i],f[j]+1);`

最后的f[1-n]就是以每个数结尾的上升子序列的最大长度 只需要在里面再维护一个max即可

这个思想和kmp模式串内部求next数组很像

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int a[N],f[N];

int n;

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[j]<a[i])

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

        }

    }

    int res=0;

    for(int i=1;i<=n;i++)

        res=max(res,f[i]);

    cout<<res;

    return 0;

}
```

输出路径

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010;

int a[N],f[N];

int g[N];//记录路径

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    for(int i=1;i<=n;i++){

        f[i]=1;

        g[i]=0;

        for(int j=1;j<i;j++){

            if(a[j]<a[i]){

                if(f[j]+1>f[i]){

                    f[i]=f[j]+1;

                    g[i]=j;

                }

            }

        }

    }

    int k=1;//记录最优解的下标

    for(int i=1;i<=n;i++)

        if(f[k]<f[i])

            k=i;

    cout<<f[k]<<endl;

    //可倒推路径 一共是f[k]个值

    for(int i=0,len=f[k];i<len;i++){

        cout<<a[k]<<" ";//首先k是答案所在的位置 a[k]保存的就是路径

        k=g[k];//g[k]记录的是从哪走到k位置 所以让k往上一个退（类似next数组）

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最短编辑距离|最短编辑距离]] 🏠 [[00-刷题理模型]] ➡️ [[最长上升子序列2|最长上升子序列2]]