LeetCode300——最长递增子序列

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence

动态规划

定义转移矩阵和转移规则，设dp[i]是以数组第i个元素结尾的最长递增子序列的长度，那么可以找到dp[i]与之前的元素关系是，如果nums[i]大于nums[j]，j<i，则dp[i] = max{dp[j] + 1}，j < i。复杂度。
代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 1);

        for (int i = 0; i < n; i++) {
            if (i == 0) dp[i] = 1;
            else {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        dp[i] = std::max(dp[j] + 1, dp[i]);
                    }
                }
            }
            cout << dp[i];   
        }

        return *std::max_element(dp.begin(), dp.end());

    }
};

贪心+二分

主要思路是直观的想法是要让递增数组足够长，那么需要前面的数尽量小，去维护这样一个递增的数组。通过遍历给定的整数数组，如果当前的元素比维护数组的元素大，那么肯定可以添加进去，如果不是，说明维护数组有的元素比当前的元素大，需要做一个替换用当前元素覆盖掉第一个比它大的元素（这样做的话后续递增序列才有可能更长，即使并没有更长，这个覆盖操作也并没有副作用，当然这个覆盖操作可能会让最终的结果数组值并不是最终的递增序列值），这样最后得到的维护数组长度即为目标长度，证明可以看问题讨论区，时间复杂度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            if (i == 0) {
                ans.push_back(nums[i]);
            }
            else {
                auto it = std::lower_bound(ans.begin(), ans.end(), nums[i]);
                if (it == ans.end()) ans.push_back(nums[i]);
                else *it = nums[i];
            }
        }
        return ans.size();

    }
};

相关题目