Standard Bar Dynamic Programming · DP on LIS O(n^2) · O(n)
The relay planner's follow-up request: don't just count the longest handoff chain — print one. Dispatch wants the actual station tags in order so drivers can rehearse the run. When several chains tie for longest, any one of them is acceptable.
Input: An integer n and an array arr of n integers.
Output: Return one longest strictly increasing subsequence of arr as an array of its values.
1 <= n <= 10001 <= arr[i] <= 10^5Input: {"n":8,"arr":[10,9,2,5,3,7,101,18]}
Output: [2,3,7,18]
One valid length-4 chain; [2, 5, 7, 101] is equally correct.
Input: {"n":6,"arr":[5,4,11,1,16,8]}
Output: [5,11,16]
Three rising tags; [4, 11, 16] and [5, 11, 16] both qualify.