FunctionRacerProblemsRace

Longest Climbing Chain

MediumDynamic programmingPython, JavaScript, TypeScript, Java, C++

From the list heights, pick a chain of entries that keeps their original left to right order and is strictly increasing, meaning every entry is larger than the entry picked before it. The chain does not need to use neighboring entries. Return the length of the longest such chain. Any single entry is a chain of length 1, and an empty list gives 0.

Example 1

heights [5,1,6,2,7,3]
returns 3

5, 6, 7 and 1, 2, 3 are both climbing chains of length 3, and no chain of length 4 exists.

Example 2

heights [9,8,7]
returns 1

Every entry is smaller than the one before it, so a chain can hold only one entry.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems