最长增长子序列（串），最大公共子序列（串），

深藏阁楼爱情的钟 2022-05-11 09:44 173阅读 0赞

[300. Longest Increasing Subsequence][]

子序列，不需要连续的。

思路一：传统的dp，dp\[i\]表示前i个数且以第i个数字结尾的最长增长子序列，遍历数组，dp\[i\] = max(dp\[i\], dp\[j\] + 1) if nums\[i\] > nums\[j\], j from 0 to i

思路二：维护一个数组，vec\[i\]表示，当递增序列长度是i的时候最后一个数的最小值

代码：

class Solution {
    public:
        int lengthOfLIS(vector<int>& nums) {
            // version 1: traditonal dp
            /*
            vector<int> dp(nums.size(), 1);
            int res = 0;
            for (int i = 0; i < nums.size(); ++i) {
                for (int j = 0; j < i; ++j) {
                    if (nums[i] > nums[j]) {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                res = max(res, dp[i]);
            }
            return res;
            */
            // version 2: DP & BS
            /*
            vector<int> dp;
            for (int i = 0; i < nums.size(); ++i) {
                int left = 0, right = dp.size();
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (dp[mid] < nums[i]) left = mid + 1;
                    else right = mid;
                }
                if (right >= dp.size()) dp.push_back(nums[i]);
                else dp[right] = nums[i];
            }
            return dp.size();
            */
            // version 3: DP & lower_bound function in C++ STL instead of BS
            vector<int> v;
            for (auto a : nums) {
                auto it = lower_bound(v.begin(), v.end(), a);
                if (it == v.end()) v.push_back(a);
                else *it = a;
            }
            return v.size();
        }
    };

[300. Longest Increasing Subsequence]: https://leetcode.com/problems/longest-increasing-subsequence/description/