Implement longest increasing subsequence using the patience sorting approach in O(n log…
- User
Implement longest increasing subsequence using the patience sorting approach in O(n log n). Maintain a list of active pile tails and for each number binary search to find the first pile top >= the number and replace it, or start a new pile.
- Assistant
Implementing LIS with patience sorting
The algorithm maintains active pile tails representing the smallest possible tail for increasing subsequences of each length. For each number, it binary searches the tails to find the first tail ≥ the number to replace or appends it if none is found. The final number of tails is the length of the longest increasing subsequence.
from bisect import bisect_left def longest_increasing_subsequence(nums): tails = [] for num in nums: i = bisect_left(tails, num) if i == len(tails): tails.append(num) else: tails[i] = num return len(tails) # Example usage if __name__ == "__main__": sequence = [10, 9, 2, 5, 3, 7, 101, 18] print(longest_increasing_subsequence(sequence)) # Output: 4 ```</think> A patience‑sorting based LIS keeps, for every possible subsequence length, the smallest tail value seen so far. When a new element arrives you either start a new pile (subsequence) or replace the tail of an existing one; the length of the pile list at the end is the LIS length. Here's an \(O(n\log n)\) implementation in Python: ```python from bisect import bisect_left def lis_length(seq): tails = [] # tails[i] = minimum possible tail of an IS of length i+1 for x in seq: # find leftmost tail >= x i = bisect_left(tails, x) if i == len(tails): tails.append(x) # start a new pile else: tails[i] = x # replace pile top return len(tails) # example data = [10, 9, 2, 5, 3, 7, 101, 18] print(lis_length(data)) # prints 4 (e.g. [2,3,7,18])If you prefer to see the binary search explicitly:
def lis_length(seq): tails = [] for x in seq: lo, hi = 0, len(tails) while lo < hi: mid = (lo + hi) // 2 if tails[mid] >= x: hi = mid else: lo = mid + 1 if lo == len(tails): tails.append(x) else: tails[lo] = x return len(tails)
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.