Longest Increasing Subsequence ​

leetcode 300. Longest Increasing Subsequence

Intuition : DP Buttom-up Approach ​

Let dp[i] is the longest increase subsequence of nums[0..i] which has nums[i] as the end element of the subsequence.

Code ​

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

Complexity Analysis ​

Time : O(n^2)

Space : O(n)

Faster solution : Greedy + binary search ​

Read the code first, and you'll discover without else handling exception is a bad idea.

Take 10,9,10 as an example, without else, we will only have {10} in res, By observation, we might want to change res[0] to 9 when it loops to the second number (9).

Vice versa, when this example occurs in either the middle of the nums or the res.

int lengthOfLIS(vector<int>& nums) {
    vector<int> res;
    for(int& i : nums) {
        if(res.empty() || res.back() < i)
            res.push_back(i);
        else
            // find the smallest number >= i in res.
            *(lower_bound(begin(res), end(res), i)) = i;
    }
    return res.size();
}

Complexity Analysis ​

Time : O(n*log(n))

Space : O(n)

UVA example : ​

UVA - 437 The Tower of Babylon