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

DP14 最长上升子序列(一)

描述 给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。 所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。 我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 iii 和 jjj 满足 i<ji<ji<j 且 arri≥arrjarr_i \geq arr_jarri​≥arrj​。 数据范围： 0≤n≤10000\leq n \leq 10000≤n≤1000 , ∣arri∣≤109 |arr_i| \le 10^9 \ ∣arri​∣≤109 要求：时间复杂度 O(n2)O(n^2)O(n2)， 空间复杂度 O(n)O(n)O(n) 输入描述： 第一行输入一个正整数 n ，表示数组的长度 第二行输入 n 个整数表示数组的每个元素。 输出描述： 输出最长严格上升子序列的长度 示例1 输入：

7 6 3 1 5 2 3 7

输出：

4

说明：

该数组最长上升子序列为 [1,2,3,7] ，长度为4

CPP参考:

#include<vector>
using namespace std;

class Solution{

    public:
        int lengthOfSeq(vector<int> &nums){
            int result =1;
            vector<int> dp(nums.size(),1);
            for (int i =1;i< nums.size();i++){
                for (int j= 0;j<i;j++){
                    
                    if(nums[i] > nums[j]){
                        dp[i] =max(dp[i],dp[j]+1);
                    }
                    
             
                }
                
                 if(dp[i] > result){
                        result =dp[i];
                    }
            }
            
            return result;
        
    }
};

int main(){
    
    int n,val;
    cin >>n;
    
    vector<int> nums(n);
    for (int i =0;i<n;i++){
        cin >> val;
        nums[i] = val;
    }
    Solution solu;
    cout << solu.lengthOfSeq(nums) <<endl;
    return 0;
}