💬 Discord
Sign In
NeetCode #672LC-300Medium1-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#672 · #300 · Longest Increasing Subsequence(最长递增子序列)

📌 Problem Statement & Constraints

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements. Constraints: 1 <= nums.length <= 2500, -10^4 <= nums[i] <= 10^4. The follow-up asks for an O(n log n) solution.

💡 Core Algorithmic Approaches

  1. The O(n^2) DP defines dp[i] as the length of the longest increasing subsequence ending at i, with dp[i] = 1 + max(dp[j]) over j < i and nums[j] < nums[i].
  2. The O(n log n) approach is patience sorting: keep an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1.
  3. For each value x, binary search for the first tail that is at least x and replace it; if none exists, append x.
  4. The length of tails is the answer, even though tails itself is not necessarily a valid subsequence.

💻 Benchmark Python3 Implementation

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        from bisect import bisect_left
        tails = []                     # tails[k] = smallest tail of an LIS of length k+1
        for x in nums:
            i = bisect_left(tails, x)  # first index with tails[i] >= x
            if i == len(tails):
                tails.append(x)        # x extends the longest subsequence
            else:
                tails[i] = x           # x lowers the tail for that length
        return len(tails)


# O(n^2) DP variant
class Solution2:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n) with patience sorting; O(n^2) for the DP variant.
💾 Space Complexity
O(n): the tails array (or the DP array).

⚠️ Interview Pitfalls & Follow-ups

  • Using bisect_right instead of bisect_left: the subsequence must be strictly increasing, so equal values must not extend it; the lower bound is correct.
  • Treating tails as a real subsequence: it only encodes lengths, so its elements can come from unrelated positions, as in [1, 5, 2, 6].
  • Sorting nums first: that destroys the subsequence order, which is the whole constraint.
  • Returning max(dp) in the patience version: there is no dp array; the answer is len(tails).