动态规划DP 最长上升子序列模型 最长上升子序列（题目分析+C++完整代码）

概览检索
动态规划DP 最长上升子序列模型

最长上升子序列

原题链接

AcWing 895. 最长上升子序列

题目描述

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

输入格式
第一行包含整数 N。
第二行包含 N个整数，表示完整序列。

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

数据范围
1≤N≤1000，−109≤数列中的数≤109

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

题目分析

闫氏DP分析法

集合的划分

以a[k]为例，则第k类中的上升子序列：
···a[k],a[i]
···a[k],a[i]
···
···a[k],a[i]
有很多组以a[k]为倒数第二个数，a[i]为结尾的序列，而其中的最长序列即为**···到a[k]的最大值max 再加上1(a[i])，即等价为 f[a[k]] +1**。

可知，f[i]则取所有a[i]结尾中长度最长的序列即可。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n;
int a[N],f[N];  //a存储原始数据，f存储状态
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    //遍历以a[i]结尾的序列
    for(int i=1;i<=n;i++){
        f[i]=1;  //该序列中只有a[i]，以a[i]结尾,长度为1
        //遍历在以a[i]结尾的序列下，倒数第二个数（即前一个数）为a[j]的序列
        for(int j=1;j<i;j++)
            if(a[j]<a[i])  //如果满足递增（前一个个数a[j]大于当前数a[i]）
                f[i]=max(f[i],f[j]+1);  //则进行更新，取最大值
    }
    int res=0;
    //遍历以a[0]~a[n]结尾的最大上升子序列，其中的最大值即为所求值
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    printf("%d",res);
    return 0;
}