300 - Longest Increasing Subsequence

解法一 - 暴力法

這題的暴力法就是每一種 increasing sequence 都試試看,然後看哪個最長。所以在處理每一個數字時,都有要用或不要用兩種選擇,但要用只能在 nums[curIdx] > nums[prevIdx] 的情況下才能用,不然就不是 increasing sequence 了。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        return findLIS(nums, 0, -1);
    }

private:
    int findLIS(vector<int>& nums, int curIdx, int prevIdx) {
        if(curIdx == nums.size())
            return 0;

        int c1 = 0;
        // include the nums[curIdx] when it is larger than the previous included value
        if(prevIdx == -1 || nums[curIdx] > nums[prevIdx]) {
            c1 = 1 + findLIS(nums, curIdx+1, curIdx);
        }

        int c2 = findLIS(nums, curIdx+1, prevIdx);

        return max(c1, c2);
    }
};

這個做法會 TLE。

解法二 - Memoization

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<vector<int>> memo(nums.size()+1, vector<int>(nums.size()+1, -1));
        return findLIS(memo, nums, 0, -1);
    }

private:
    int findLIS(vector<vector<int>>& memo, vector<int>& nums, int curIdx, int prevIdx) {
        if(curIdx == nums.size())
            return 0;

        if(memo[curIdx+1][prevIdx+1] == -1) {
            int c1 = 0;
            // include the nums[curIdx] when it is larger than the previous included value
            if(prevIdx == -1 || nums[curIdx] > nums[prevIdx]) {
                c1 = 1 + findLIS(memo, nums, curIdx+1, curIdx);
            }
            int c2 = findLIS(memo, nums, curIdx+1, prevIdx);

            memo[curIdx+1][prevIdx+1] = max(c1, c2);
        }

        return memo[curIdx+1][prevIdx+1];
    }
};

這樣解就可以過,不過效率不彰:

Runtime: 500 ms, faster than 5.76% of C++ online submissions for Longest Increasing Subsequence. Memory Usage: 111.5 MB, less than 6.25% of C++ online submissions for Longest Increasing Subsequence.

解法三 - DP

首先決定一下狀態,我們可以定義 dp[i] = 到數字 i 時,最長的 increasing sequence 是多長。所以,

dp[i] = dp[j]+1 if (dp[j]+1 > dp[i] && nums[i] > nums[j]) for all j < i

因為只要 nums[i] 比 nums[j] 大,那就可以跟到 nums[j] 為止的 increasing sequence 形成更大的 sequence,但我們根本無法知道比 i 小的 j 裡面,哪個有最長的 increasing subsequence,就算某個 j 有最長的 increasing sequence,也要 nums[j] < nums[i] 才能繼續接下去。

實作如下:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.empty()) return 0;

        vector<int> dp(nums.size());
        dp[0] = 1;

        int maxLen = 1;
        for(int i=1; i<nums.size(); i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(nums[j] < nums[i] && dp[j]+1 > dp[i]) {
                    dp[i] = dp[j]+1;
                    maxLen = max(maxLen, dp[i]);
                }
            }
        }

        return maxLen;
    }
};

results matching ""

    No results matching ""