Patience sorting: track the smallest possible tail for an increasing subsequence of each length.
Maintain array tails where tails[len-1] is the minimum tail of an LIS of length len.
For each x, binary search lower_bound position and replace/append.
Keeping tails minimal preserves the ability to extend to longer subsequences; length of tails is LIS length.
Patience sorting: track the smallest possible tail for an increasing subsequence of each length.
Maintain array tails where tails[len-1] is the minimum tail of an LIS of length len.
For each x, binary search lower_bound position and replace/append.
Keeping tails minimal preserves the ability to extend to longer subsequences; length of tails is LIS length.