Standard Bar Dynamic Programming · DP on LIS O(n log n) · O(n)
A logistics relay passes parcels through n stations, and station i only accepts a parcel whose priority tag is strictly higher than the one stamped at the previous stop. The route planner wants the longest possible chain of handoffs for a given tag sequence. Tags can be visited out of physical order — only the relative ranking matters.
Input: An array nums of n integers.
Output: Return the length of the longest strictly increasing subsequence of nums.
1 <= n <= 2500-10^4 <= nums[i] <= 10^4Input: {"nums":[10,9,2,5,3,7,101,18]}
Output: 4
2, 3, 7, 18 (or 2, 5, 7, 101) — four strictly rising tags.
Input: {"nums":[0,1,0,3,2,3]}
Output: 4
0, 1, 2, 3 uses both zeros correctly — one per rising step.