哪位大佬给我讲讲这段代码什么意思,老师讲的没听懂,求求了(QaQ)

chenxinuo @ 2024-07-09 19:49:48

#include<bits/stdc++.h>
using namespace std;
int f[10100],a[10100],n;
int ans;
int main() 
{
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i];f[i]=1;}
    for(int i=2;i<=n;i++)
    { 
        for(int j=1;j<i;j++)
        {
            if(a[i]>a[j]) f[i]=max(f[i], f[j]+1);
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,f[i]);
    cout<<ans;
    return 0;
}

by I_will_AKIOI @ 2024-07-09 19:54:37

首先 f_i 表示以 i 结尾的最长上升子序列长度。然后就是枚举 j=[1,i-1]，如果满足 a_i>a_j，那么就说明可以把 a_i 接在 a_j 的后面，也就是一个上升的子序列。然后求 \max 的操作是因为要取最长的上升子序列。

by WZWZWZWY @ 2024-07-09 19:54:49

@chenxinuo 你就不能再去问老师吗

因为是从左往右上升的，所以若要从a[j] 转移过来，要保证 i>j 且 a[i]>a[j]

因为求最长，所以 f[i]=max(f[i], f[j]+1);

by chenxinuo @ 2024-07-09 19:58:48

@I_will_AKIOI @WZRYWZWY 屑屑dalao 懂了

by chenxinuo @ 2024-07-09 20:01:02

已关注