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

//简单的dp
/*
记dp[i]为以arr[i]为结束的最长的子串长度
那么：
dp[i+1] = while(arr[k]<arr[i+1]):max(dp[k0]、dp[k1].....dp[ki]) + 1 //加上自己
最后求最大的dp即可
*/
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n,arri;
    vector<int>arr;
    cin>>n;
    if(n==0){
        cout<<0;
        return 0;
    }
    for(int i=0;i<n;++i){
        cin>>arri;
        arr.push_back(arri);
    }
    vector<int> dp(n,1);
    int top=arr[0];
    int res = 1;
    for(int j=0;j<n-1;++j){
        for(int k=0;k<j+1;++k){
            if(arr[k]<arr[j+1])dp[j+1] = max(dp[j+1],dp[k]+1);
        }
        res = max(dp[j+1],res);
    }
    cout<<res;
    return 0;
}
// 64 位输出请用 printf("%lld")