[LeetCode] Longest Increasing Subsequence

  • 时间:
  • 浏览:0

If you look at the else part carefully, you may notice that it can be done using lower_bound. So we will have a much shorter code, like this one.

Then the length of the LIS of nums is just the maximum value in lens. The code is as follows.

A typical O(n^2) solution uses dynamic programming. Let's use lens[j] to denote the length of the LIS ending with nums[j]. The state equations are

lens[0] = 1

The O(nlogn) solution is much more complicated. Try to read through the explanation of it in GeeksforGeeks first. The code is as follows.

lens[j] = max_{i = 0, 1, 2, ..., j - 1}(lens[j], lens[i] + 1)