(代码随想录)leetcode300. 最长递增子序列

自己还是写不出来[笑哭]

思路错了,自己死要去只遍历一遍

代码随想录答案:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() <= 1)return nums.size();
        vector<int>dp(nums.size(), 1);//所有元素都是1长度
        //dp[i]表示i前(包括i)最大的连续增长子序列长度
        int result = 0;
        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);//记录dp[i]的最大值
            }
            if(dp[i] > result)result = dp[i];
        }
        return result;
    }
};

似乎前面贪心算法做过,但是我想不出来贪心的做法[裂开]

力扣贪心解法:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = 1, n = (int)nums.size();
        if (n == 0) {
            return 0;
        }
        vector<int> d(n + 1, 0);
        d[len] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {
                int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos + 1] = nums[i];
            }
        }
        return len;
    }
};

673. 最长递增子序列的个数

这道题的进阶

class Solution {
public:
    //count[i]记录了以nums[i]为结尾的字符串，最长递增子序列的个数。
    //dp[i]记录了i之前（包括i）最长递增序列的长度。
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.size() <= 1)return nums.size();
        vector<int>dp(nums.size() + 1, 1);
        vector<int>count(nums.size() + 1, 1);
        int maxCount = 0;
        for(int i = 1;i < nums.size();++i){
            for(int j = 0;j < i;++j){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        count[i] = count[j];
                    }else if(dp[j] + 1 == dp[i]){
                        count[i] += count[j];
                    }
                    dp[i] = max(dp[i], dp[j] + 1);
                }
                if(dp[i] > maxCount)maxCount = dp[i];
            }
        }
        int result = 0;
        for(int i = 0;i < nums.size();++i){
            if(dp[i] == maxCount)result += count[i];
        }
        return result;        
    }
};

维护两个数组,简直要把我难哭了,主要是这个count的含义太难想了

解释还是老实去看原文吧,期待自己二刷该题能ac