leetcode(300)-Longest Increasing Subsequence(最長増分子シーケンス)

参考Python解法:動的計画-最長増分子シーケンス(LIS)
原題位置:Longest Increasing Subsequence|LeetCode OJ
タイトルの説明:

は厳格に増加した.

サブシーケンスは連続を要求しない.

解法1,O(n 2)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
    if (nums.size() == 0) return 0;
        vector<int> dp(nums.size(), 1);
        int res = 1;
        for (int i = 1; i < nums.size(); ++i){
                        //       ，                  ；
            for (int j = 0; j < i; ++j){
                if (nums[j] < nums[i]){
                    dp[i] = max(dp[i], 1+dp[j]);
                                //      j     dp[i]    
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

解法2:O(nlogn)
まず配列endsを構築し、最初の要素を入れて、その後の要素を比較します.

遍歴した新しい要素がends配列の最初の要素より小さい場合、最初の要素を新しい要素に置き換えます.

遍歴した新しい要素がends配列の末尾要素よりも大きい場合は、この新しい要素をends配列の末尾に追加します(元の末尾要素を上書きしないことに注意してください).

遍歴した新しい要素がends配列の最初の要素より大きく、最後の要素より小さい場合、このとき二分ルックアップ法でこの新しい要素よりも小さくない最初の位置を見つけ、位置の元の数字を上書きし、

このようにしてnums配列が完全に遍歴するまで、ends配列の長さは私たちが要求するLISの長さであり、特にends配列の値は実際のLISではない可能性があることに注意してください.例えば、入力配列numsが{4,2,4,5,3,7}であれば、計算後のends数群は{2,3,5,7}であり、元の配列のLISではないことがわかります.長さが等しいだけなので、くれぐれも注意してください.

class Solution(object):
    def lengthOfLIS(self, nums):
        n = len(nums)
        if n == 0: return 0
        ends = [nums[0]]
        for i in range(1, n):
            if nums[i] < ends[0]:
                ends[0] = nums[i]
            elif nums[i] > ends[-1]:
                ends.append(nums[i])
            else:
                lo, hi = 0, len(ends)
                while lo < hi:
                    mi = (lo + hi)//2
                    if nums[i] > ends[mi]: lo = mi + 1
                    else: hi = mi
                ends[hi] = nums[i]
        return len(ends)

解法3:より明確な二分検索
上記の方法とよく似ていますが、まず空のdp配列を確立し、元の配列を遍歴し始めます.遍歴した数字ごとに、dp配列で最初の数字を探します.もしこの数字が存在しなければ、直接dp配列の後ろに遍歴した数字を加えます.もし存在するならば、この数字を現在遍歴している数字に更新し、最後にdp数字の長さを返すとよいが、上記の方法と同様に、特にdp配列の値が実際のLISではない可能性があることに注意する.コードは次のとおりです.

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp;
        for (int i = 0; i < nums.size(); ++i){

            int lo = 0, hi = dp.size();
            while (lo < hi){
                int mi = (lo + hi)/2;
                if (dp[mi] < nums[i]) lo = mi + 1;
                else hi = mi;
            }
            if (hi == dp.size())
                dp.push_back(nums[i]);
            else dp[hi] = nums[i];
        }
        return dp.size();
    }
};

4.標準ライブラリSTLのアルゴリズムによる二分検索部分の実現
lower_boundは、シーケンス内の最初の値以上の要素の位置を返します.

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