题解 | Redraiment的走法

转换成求最长递增子序列 使用一维动态规划即可

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> height(n);
    for(int i = 0; i < n; ++i) {
        cin >> height[i];
    }
    //相当于求最长递增子序列 使用动态规划去求
    //dp[i]表示以height[i]结尾的最长递增子序列的长度
    vector<int> dp(n, 1); 
    for(int i = 1; i < n; ++i) {
        //对于每一个i 用0-i中的每一个dp[j]去更新dp[i]
        for(int j = 0; j < i; ++j) {
            if(height[i] > height[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    return 0;
}