300. Longest Increasing Subsequence

Description

Given an unsorted array of integers, find the length of longest increasing subsequence. (For this question, it’s stricly increasing.)

Example:

Input: [10,9,2,5,3,7,101,18]

Output: 4

Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• our algorithm should run in O(n²) complexity.

Follow up:

Could you improve it to O(nlogn) time complexity?

Idea

DP.

1. O(n²)

Consider that dp[i] represents the longest increasing subsequence ending at i. First initiate the array with value 1. Then for every number j less than i:

• If dp[j] < dp[i], dp[i] = max(dp[i], dp[j] + 1) (because dp[i] contributes to LIS)
• otherwise, dp[i] = dp[i]
• Finally, the result is the maximum of array dp

The time complexity is O(n²)

2. O(nlogn)

Consider we maintain a vector dp and dp[i] means the least value for LIS with length (i + 1).

• If current num is greater than any number in dp, push it to dp
• insert current num to the the lower_bound index.

Notice that dp is actually ordered, an we can search num in O(logn) time. Then the total time complexity is O(nlogn). And the result is the size of dp.

Solution

// O(n^2)
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        vector<int> dp(nums.size(), 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], dp[j] + 1);
                }
            }
        }
        int res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            res = max(res, dp[i]);
        }
        return res;
    }
};

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