线性动态规划-最长递增子序列(LIS)

数据结构与算法第十章动态规划线性动态规划-最长递增子序列(LIS)

最长不下降子序列(Longest Increasing Subsequence)。

给定一个n个数的序列A，问最长的不下降子序列长度为多少。
输入样例：
8
2 7 3 1 5 8 9 4
输出样例：
5
不下降子序列为2 3 5 8 9
方法：依次求出以原序列中每个元素分别为子序列结尾时的最长不下降子序列。

#include <iostream>
using namespace std;

const int Max=1000;
int A[Max],F[Max],N,ans;
int main(){
    cin>>N;
    for (int i =1; i <=N; i++)cin>>A[i];
    
    F[1]=1;
    ans=1;
    for (int i =2; i <=N; i++){
        F[i]=1;
        for (int j = 1; j <=i-1; j++){
            if(A[j]<=A[i]&&F[j]+1>F[i])F[i]=F[j]+1;
        }
        if(F[i]>ans)ans=F[i];
    }
    cout<<ans<<endl;   
}