C++DP：最长上升子序列 LIS

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    // dp[i] = 以 a[i] 结尾的最长上升子序列长度
    vector<int> dp(n, 1);
    int ans = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(a[j] < a[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return 0;
}

✅ 输入样例

6
10 9 2 5 3 7

✅ 输出样例

3