Finding the length of the longest strictly increasing subsequence is the classic LIS problem. Here you must return an actual subsequence.
Write lis_sequence(nums) -> list[int]: the values of one longest strictly increasing subsequence of nums, in their original order. A subsequence keeps the original order but may skip elements. If several subsequences have the maximum length, any of them is accepted. Return [] for an empty list.
lis_sequence([3, 1, 4, 1, 5, 9, 2, 6]) # e.g. [3, 4, 5, 9] (or [1, 4, 5, 6], ...; length 4)
lis_sequence([5, 5, 5]) # [5] strictly increasing, so equal values can't chain
lis_sequence([9, 7, 4, 2]) # e.g. [2]
Constraints: 0 <= len(nums) <= 200_000, -10**9 <= nums[i] <= 10**9.
The O(n²) DP is too slow for 200k elements; aim for O(n log n).
Show hint
start from the O(n log n) way of finding the length (the smallest possible tail for each length, updated by binary search). To rebuild the sequence, also remember which element sits in each slot and, for every element, which earlier element it extended.