300. Longest Increasing Subsequence

• Difficulty: Medium

• Topics: Binary Search, Dynamic Programming

• Similar Questions:

  • Increasing Triplet Subsequence

  • Russian Doll Envelopes

  • Maximum Length of Pair Chain

  • Number of Longest Increasing Subsequence

  • Minimum ASCII Delete Sum for Two Strings

Problem:

Given an unsorted array of integers, find the length of longest increasing subsequence.

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.
• Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Solutions:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() == 0)   return 0;
        map<int, int> dp;
        for (auto& num : nums) {
            if (dp.empty()) {
                dp[num] = 1;
                continue;
            }
            if (dp.count(num))  continue;
            auto it = dp.lower_bound(num);
            if (it == dp.end()) {
                dp[num] = prev(it)->second + 1;
            } else {
                dp[num] = it->second;
                dp.erase(it);
            }
        }

        return dp.rbegin()->second;

    }
};