Longest Increasing Subsequence

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^2) complexity.

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

Constraints etc

  • Your algorithm should run in O(n^2) or better complexity.
  • subsequence need not consist of adjacent numbers

Accepted quadratic

TBD

Accepted logarithmic

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    int get_index(vector<int>& vec, int val) {
      int low = 0;
      int high = vec.size() - 1;
      while (low <= high) {
          int mid = low + (high - low) / 2;
          if (vec[mid] < val) {
               low = mid + 1;
          } else if (vec[mid] > val) {
               high = mid - 1;
          } else return mid;
      }
      return low;
    }
    void pr(vector<int>& vec) {
      cout << "{ ";
      for (auto e: vec) {
        cout << e << ", ";
      }
      cout << " } \n";
    }
public:
    int lengthOfLIS(vector<int>& nums) {
      vector<int> tails;

      for (int i = 0; i < nums.size(); i++) {
        //cout << "index = " << i << endl;
        int pos = get_index(tails, nums[i]);
        //cout << "pos = " << pos << endl;
        //cout << " Before :";
        //pr(tails);
        if (pos == tails.size()) { tails.push_back(nums[i]); }
        else { tails[pos] = nums[i]; }
        //cout << " After :";
         //pr(tails);
      }
      return tails.size();

    }
};

Understanding the resultant array

Given this example [8, 2, 5, 1, 6, 7, 9, 3]
And the resultant array sub = [1, 3, 6, 7, 9]

Let’s look at the each of the values in sub and use the given input array to see the possible subsequences for each size.
At index 0, 1 is the smallest tail that can give us a subsequence of size 1
At index 1, 3 is the smallest tail that can give us a subsequence of size 2, [1,3] or [2,3]
At index 2, 6 is the smallest tail that can give us a subsequence of size 3, [2,5,6]
At index 3, 7 is the smallest tail that can give us a subsequence of size 4, [2,5,6,7]
At index 4, 9 is the smallest tail that can give us a subsequence of size 5, [2,5,6,7,9]

For index 0, we can basically pick any element. But, 1 is the smallest value possible. By ordering the elements in sub in ascending order we are trying to ensure that the largest number in the subsequence ending at each position (i.e. the tail) is as small as possible. This means that we can maximize the probability of being able to pick subsequent subsequences of length 4, 5 etc.
When we select 9 for a subsequence of length 1, we can no longer pick any other increasing numbers that result in an increasing subsequence.

As another example, for subsequence of size 3, the possible subsequences are [2,5,6] [2,6,7] [2,7,9] [5,6,7] [1,6,7] [6,7,9]. Our algorithm ended up picking [2,5,6] by placing the 6 at that position.