[LeetCode] Longest Increasing Subsequence

  • 时间:
  • 浏览:1
  • 来源:UU直播快三官方_大发UU直播快3

lens[j] = max_{i = 0, 1, 2, ..., j - 1}(lens[j], lens[i] + 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.

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

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.