Given an array, the machine must find the length of the longest subsequence whose values strictly increase. The elements do not need to be contiguous, but their relative order must match the original array.
The key insight is the tails array from patience sorting: tails[k] stores the smallest possible tail value of any increasing subsequence of length k+1. Because tails is monotonically increasing, the machine can binary search it for every new element, which is what makes this faster than the O(n^2) quadratic DP.
The approach runs in three steps. First, maintain an empty tails list. Second, for each element, binary search for the first position where the element could replace an existing tail, then either overwrite that position or append. Third, return the length of tails. Time is O(n log n) and space is O(n).
The trickiest edge case is duplicate values: the problem demands a strictly increasing subsequence, so a value equal to an existing tail must never extend it. Using a leftmost insertion point (bisect_left) makes the machine replace instead of append, which is why all-equal input like [7,7,7] correctly yields length 1 rather than 3.
from bisect import bisect_left
def lengthOfLIS(nums):
tails = []
for x in nums:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)