Problem ID: 300

Title: Longest Increasing Subsequence

Difficulty: Medium


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].


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


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


class Solution {
    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) {
            auto i = b_search(seq, num);
            if (seq[i] == num) continue;
            seq[i] = num;
        return seq.size();