Leetcode 300. 最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

一开始想用dfs＋剪枝，超时

class Solution {
public:
    unordered_map<int,int> max_length;
public:
    int search(vector<int>& nums,int length,int index,int last){
        if(index == nums.size())
            return length;
        if(max_length.count(last) == 0)
            max_length.insert({last,length});
        else if(length<max_length[last])
            return INT_MIN;
        else
            max_length[last] = length; 
        if(last>=nums[index])
            return search(nums,length,index+1,last);
        return max(search(nums,length+1,index+1,nums[index]),search(nums,length,index+1,last));
    }
    int lengthOfLIS(vector<int>& nums) {
        return search(nums,0,0,INT_MIN);
    }
};

直接DP

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int result = 0;
        vector<int> maxLength(nums.size());
        for(int i = 0;i<nums.size();i++){
            for(int j = i - 1;j>=0;j--){
                if(nums[i]>nums[j])
                    maxLength[i] = max(maxLength[j]+1,maxLength[i]);
            }
        }
        for(auto i : maxLength){
            result = max(result,i);
        }
        return result+1;
    }
};

但都不是最优解

题解：300. 最长递增子序列 - 力扣（LeetCode）