题解 | #Redraiment的走法#

#include <iostream>
#include <vector>
using namespace std;
//动态规划经典题目，寻找数组中的最长递增子序列元素数
/*1)dp[i]表示以nums[i]为结尾的子数组中，最长递增子序列的元素数
2）递推：i先遍历所有元素，j来遍历0～i(即j是为了找I的所有子序列)，if(nums[j]<nums[i])子序列中有递增的元素出现，则dp[i]=max(dp[j]+1,dp[i])   (dp[i]要去到i之前所有子序列中最大的数字，因为没有一个最大值就给dp[i]赋值了，再有更大的长度出现就覆盖赋值)
3）初始化：dp[i]=1;dp[0]=1;dp【0】只有一个元素，长度一定是1，dp【i】最少是1
4）递推：从小到大递推，dp[i]的产生依赖于之前的dp[i]的值（在下一个循环里，之前的i由j遍历了，dp[i]的数值变为dp[j]参与计算新的dp[i]，所以一定要从小到大遍历，不断提供计算新的dp【i】所需要的dp{j}的值）
*/
int main() {
    int n;
    cin>>n;
    int nums[n];
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    vector<int>dp(n,1);

    int Maxmum=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(nums[j]<nums[i]){
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
        //cout<<dp[i]<<" ";
        if(dp[i]>Maxmum) Maxmum=dp[i];
    }
    cout<<Maxmum<<endl;

}
// 64 位输出请用 printf("%lld")