Expert · Dynamic programming · 211 of 264
Longest increasing subsequence
Find the length of the longest strictly increasing subsequence (numbers in order, not necessarily next to each other). Lists have up to 2000 numbers: aim for O(n log n) with bisect.
Input: n, then n whole numbers on one line. Output: the length.
Examples
Input
8 10 9 2 5 3 7 101 18
Output
4
Input
5 5 4 3 2 1
Output
1
Input
6 1 3 3 3 4 5
Output
4
One more test checks other inputs when you press Check.
Stuck? The idea behind dynamic programming
Break the problem into smaller ones that repeat, and keep each answer in a table so it is worked out only once.
Decide what one cell of the table means ("the best total using the first i items"), how it follows from earlier cells, and where it starts.
n = 10
ways = [0] * (n + 1)
ways[0] = 1
for i in range(1, n + 1):
ways[i] = ways[i - 1] + (ways[i - 2] if i >= 2 else 0)
print(ways[n]) # climbing 10 stairs, 1 or 2 at a timeWatch for: Fill the table in an order where every cell it needs is already filled.