题解 | 最长上升子序列(一)

#include <iostream>
using namespace std;
int a[100100],dp[10100];
int main() {
    int n;cin>>n;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        dp[i] = 1;
    }
    int res = 0,ans = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=i;j++){
            if(a[j]<a[i]){
                dp[i] = max(dp[j]+1,dp[i]);
                ans = max(ans,dp[i]);
            }
        }
    }
    cout<<ans<<'\n';
    return 0;
}
// 64 位输出请用 printf("%lld")

刚开始写的时候没有添加初始化语句，所以错误。

因为dp[i] = 1; // 每个元素自身至少构成长度为1的序列，正确的状态转移方程为：dp[i] = max(dp[i], dp[j] + 1);

活动地址https://www.nowcoder.com/discuss/726480854079250432