# 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;
    }
};