Problem

Problem ID: 300

Title: Longest Increasing Subsequence

Difficulty: Medium

Description:

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Thoughts

This is an interesting problem that does not have an intuitive solution to it.

Solution

General Idea

The key to solving this problem is observing that:

• The longest increasing subsequence will contain as many small numbers as possible
• We only need to keep track of the last number (largest so far) of when constructing the increasing subsequence

We solve this problem by tracking multiple subsequence in a single vector

• If a number is greater than the last number in the subsequence, we will just append it to the end
• If a number is smaller than the last number, this means a new subsequence can begin
  • This new subsequence can continue from all previous number that are small than it
  • As all the numbers are increasing (sorted), we can use binary search to find the most element to start the new subsequence to allow the number.
• It is always guaranteed that the last element is part of a valid subsequence
• As we “greedily” add elements into the subsequence, the size of the subsequence is answer eventhough the elements in it might not represent the exact valid subsequence

Implementation

class Solution {
public:
    int b_search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size() -1;
        while (l < r) {
            int m = (l+r)/2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m+1;
            }
        }
        return r;
    }
    int lengthOfLIS(vector<int>& nums) {
        vector<int> seq;
        for (int num : nums) {
            cout << endl;
            if (seq.empty() || seq.back() < num) {
                seq.push_back(num);
                continue;
            }
            auto i = b_search(seq, num);
            if (seq[i] == num) continue;
            seq[i] = num;
        }
        return seq.size();
    }
};