HELP

zjh20081205 @ 2024-01-15 19:11:47

by _qingshu_ @ 2024-01-15 19:34:34

@zjh20081205

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[5200010];
int f[5200010];//以 a[i] 为结尾的最长上升子序列 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(a[j]<a[i]){
                f[i]=max(f[i],f[j]+1);
            }
        }
        ans=max(ans,f[i]);
    }
    cout<<ans;
}

by _qingshu_ @ 2024-01-15 19:37:21

@zjh20081205

表示该状态继承由以 a_j 为结尾的最长上升子序列，因为在这个基础上又多了一个 a_i，所以需要加一。