[LeetCode] Longest Increasing Subsequence

  • 时间:
  • 浏览:0
  • 来源:uu直播快3平台

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.

lens[0] = 1

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

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

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

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