Longest rising run, not necessarily adjacent
Find the length of the longest strictly increasing subsequence (elements in order, not necessarily adjacent) of
46, 100, 95, 30, 94, 17, 26, 42, 48, 25, 29, 81, 50, 51, 64, 31, 6, 85, 1, 20.
Show hints (3)+
- For each length, track the smallest value an increasing subsequence of that length can end on.
- A new value replaces the first tail that is at least as large.
- The tails array itself is not a valid subsequence; only its length matters.
Answer
Reveal answer →Final answer
8
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading