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

这是一道动态规划题目。将其分解为子问题，即分解成求解n个 以0到n-1下标的数为结尾的子序列的最大长度的问题。
可以用一个dp数组保存每个数做结尾时对应的最大长度。
假设一个以第i个元素arr[i]结尾的子序列Si，那么Si的长度是由i在Si中的前一个元素arr[j]决定的，Si的长度就等于Sj的长度加一。

这前面一个数arr[j]必须要满足两个条件：

• arr[j]<arr[i],这样才能构成严格上升
• dp[j]的值在i之前的所有dp中最大，这样我们求的才是最大长度。

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];
    vector<int> dp(n,1);//以i下标的数为结尾的子序列的长度
    
    for(int i=1;i<n;i++){
        int mx=0;
        for(int j=0;j<i;j++){
            //每一个元素的dp值==在它之前的，比它小的元素中最大的dp值加一
            if(arr[i]>arr[j])
                mx=max(mx,dp[j]);
        }
        dp[i]=mx+1;
    }
    int res=1;
    for(int i=0;i<n;i++)
        res=max(res,dp[i]);
    cout<<res;
    return 0;
}

时间复杂度：O(n^2),空间复杂度：O(n)