Longest Climbing Chain
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
0 <= len(heights) <= 50-100 <= heights[i] <= 100
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Dynamic programming problems
- Longest Insertion LadderMedium
- Longest Mirror SubsequenceMedium
- Loot Around the Lantern RingMedium
- Lowest Photo WallMedium
- Lucky Toll TripsMedium
- No Double LeapsMedium
- One Forgiven DayMedium
- Paint the FenceMedium