hardDynamic Programming 1DPure DSA~33 min
Longest Increasing Pricing Tiers
A sequence of pricing-tier values is sampled over time. Find the longest strictly increasing subsequence of tiers — the longest run that never steps down, even if it skips entries.
Problem
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps order but need not be contiguous.
Input
An array nums of n integers (1 ≤ n ≤ 2500 for the DP form; aim for O(n log n)).
Output
An integer — the length of the longest strictly increasing subsequence.
Constraints
- Subsequence elements must be strictly increasing
- 1 ≤ n ≤ 2500
- Target O(n log n) with patience-sorting / tails array
Examples
Example 1
Input
[10,9,2,5,3,7,101,18]
Output
4
[2,3,7,18] (or [2,3,7,101]) has length 4.
Example 2
Input
[0,1,0,3,2,3]
Output
4
[0,1,2,3] is the longest increasing subsequence.