Longest Increasing Subsequence (LIS) Problem

Problem Description
The Longest Increasing Subsequence (LIS) problem requires finding the longest subsequence in a given sequence of integers such that all elements in the subsequence are strictly increasing (usually non-decreasing, but strict increasing is more common). The subsequence does not need to be contiguous, but must maintain the relative order from the original sequence. For example, for the sequence [10, 9, 2, 5, 3, 7, 101, 18], one of its longest increasing subsequences is [2, 5, 7, 101], with a length of 4.

Solution Approach
There are two classic methods to solve the LIS problem: dynamic programming (O(n²)) and greedy + binary search (O(n log n)). Below, the more efficient greedy + binary search method is explained in detail.

Step 1: Understanding the Greedy Strategy

The core of the greedy strategy is to maintain an array tail, where tail[i] represents the minimum last element among all increasing subsequences of length i+1. By continuously updating tail, we ensure it remains monotonically increasing, allowing us to use binary search to optimize the insertion process.

Step 2: Algorithm Flow

1. Initialization: Create an empty array tail to store the minimum last values for increasing subsequences of different lengths.
2. Traverse the original sequence: For each number num:
   • If num is greater than the last element of tail (i.e., it can extend the longest subsequence), append it directly to the end of tail.
   • Otherwise, find the first position in tail where the value is greater than or equal to num, and replace the value at that position with num (the goal is to make future extensions more flexible).
3. Result: The final length of tail is the length of the LIS.

Step 3: Concrete Example

Take the sequence [3, 5, 2, 8, 10, 7, 9] as an example:

• Initial tail = []
• num=3: tail is empty, add directly → tail = [3]
• num=5: greater than the last element 3 in tail, append → tail = [3, 5]
• num=2: less than 5, binary search finds the first position ≥2 (index 0), replace → tail = [2, 5]
• num=8: greater than 5, append → tail = [2, 5, 8]
• num=10: greater than 8, append → tail = [2, 5, 8, 10]
• num=7: less than 10, binary search replaces 8 → tail = [2, 5, 7, 10]
• num=9: less than 10, binary search replaces 10 → tail = [2, 5, 7, 9]

Final LIS length is 4 (note that tail may not be the optimal subsequence itself, but the length is correct).

Step 4: Implementation of Binary Search

Find the first position in tail that is greater than or equal to num (left-bound binary search):

def bisect_left(tail, target):
    left, right = 0, len(tail) - 1
    while left <= right:
        mid = (left + right) // 2
        if tail[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left  # Return insertion position

Step 5: Complete Code (Python)

def length_of_lis(nums):
    tail = []
    for num in nums:
        # Binary search for insertion position
        left, right = 0, len(tail)
        while left < right:
            mid = (left + right) // 2
            if tail[mid] < num:
                left = mid + 1
            else:
                right = mid
        # If left equals the length of tail, we need to extend
        if left == len(tail):
            tail.append(num)
        else:
            tail[left] = num
    return len(tail)

Step 6: Complexity Analysis

• Time Complexity: O(n log n), as each element requires at most one binary search.
• Space Complexity: O(n), as the length of the tail array can be at most n.

Summary
The greedy + binary search method cleverly reduces the time complexity by transforming the problem into maintaining a monotonic sequence via the minimum last value array. In actual interviews, you might also be asked to output the specific LIS sequence (which requires additional path recording), but the core logic is based on the method described above.