Before the fast bisect method, learn the plain DP it speeds up.
Implement lis_ending_at(nums: list[int]) -> list[int]. Entry i of the result is the length of the longest strictly increasing subsequence that ends with nums[i] (you may skip elements, but must keep their order, and the last element picked is nums[i]).
lis_ending_at([3, 1, 4, 1, 5, 9, 2, 6]) # [1, 1, 2, 1, 3, 4, 2, 4]
lis_ending_at([5, 5, 5]) # [1, 1, 1] equal values don't extend a subsequence
The length of the longest increasing subsequence overall is then just max(result).
Constraints: 0 <= len(nums) <= 2000, -10**9 <= nums[i] <= 10**9. An empty list gives []. O(n²) is expected.
Show hint
ends[i] = 1 + max(ends[j] for every j < i with nums[j] < nums[i]), or just 1 if there is no such j.