Skip to content
Get started

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)+
  1. For each length, track the smallest value an increasing subsequence of that length can end on.
  2. A new value replaces the first tail that is at least as large.
  3. The tails array itself is not a valid subsequence; only its length matters.

Answer

Reveal answer →

8

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions