The best chain ending here
For each position, the longest increasing run ending there is one more than the best smaller value before it. About 13 minutes.
For each number, ask: what's the longest rising chain that ends exactly on me? On its own a number is a chain of 1. Then look back at every earlier number that's smaller. You could tack yourself onto the end of its chain, one longer. Take the best of those.
Every earlier chain is already worked out by the time you get here, so each number only has to look back.
The answer can end anywhere
The longest chain doesn't have to end on the last number. In the example, 101 finishes a chain of 4, but so does 18. The last number could just as easily be tiny and end nothing interesting.
So the answer is the biggest value anywhere in the row, not the last one. Check every number, remember the best.
longest = [1] * len(nums) # each alone is a chain of 1
10, 9 and 2 have nothing smaller before them, so each is a chain of just itself: 1.
The numbers are 3, 1, 4, 2. The 3 and the 1 each start a chain of 1. How long is the best rising chain that ends on the 4?
- A2
- B3
- C1
Show the answer
2. The 4 can follow the 3 or the 1, and each of those is a chain of 1. So 1 + 1 = 2.
Longest increasing subsequence
You get a list nums of whole numbers. Return the length of the longest increasing subsequence: values taken in their original order, not necessarily next to each other, each strictly bigger than the one before.
nums = [10, 9, 2, 5, 3, 7, 101, 18] → 4
0 ≤ n ≤ 1,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000