B3637 最长上升子序列——题解

解题思路

令 f[i] 表示以第 $i$ 个数结尾的最长上升子序列长度。枚举所有更早位置 $j<i$，若 a[j]<a[i]，就可以把第 $i$ 个数接在以 $j$ 结尾的序列后面，更新 f[i]=max(f[i],f[j]+1)。

复杂度分析

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int a[5005],f[5005];
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;cin>>n;int ans=0;
    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);ans=max(ans,f[i]);}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int a[5005],f[5005]; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n;cin>>n;int ans=0; 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);ans=max(ans,f[i]);} cout<<ans<<'\n';return 0; }