Best answer ending here

A quadratic table that is easy to derive, and a logarithmic trick that is worth knowing but not guessing.

Key idea

Ending here, not anywhere

The state that works is: the best answer among those that end at position i. Not the best over the whole prefix, which sounds simpler and does not compose.

The reason is the transition. To extend an answer with element i, you need to know that the previous element is compatible with i, and only an ending-here state tells you what the previous element was.

The final answer is then the maximum over all positions, taken at the end. Forgetting that last step and returning the value at the final position is a common slip.

1values = [10, 9, 2, 5, 3, 7]2 3# Longest run ending at each index, worked out up to index 4.4best = [1, 1, 1, 2, 2]5 6i = 57extendable = [best[j] for j in range(i) if values[j] < values[i]]8print("runs that 7 can be appended to:", extendable)9print("best ending at index 5:", max(extendable, default=0) + 1)

Every earlier index with a smaller value is a candidate, so the cell costs O(n) to fill.

Key idea

The logarithmic version, and what it is really doing

Keep a list where position k holds the smallest possible value that can end an answer of length k plus one. That list is always sorted, which is what allows a binary search.

For each element, find the first entry that is not smaller than it and overwrite that entry. If no such entry exists, the element extends the list. The answer is the list's final length.

The list is not itself a valid answer, and that is the part that surprises people. Its length is correct; its contents are the best possible endings, not a reconstruction.

1from bisect import bisect_left2 3ends = [2, 5, 7]              # best ending for lengths 1, 2 and 3 so far4 5for value in (3, 9):6    position = bisect_left(ends, value)7    print(value, "lands at position", position,8          "->", "extends the list" if position == len(ends) else "overwrites " + str(ends[position]))

Overwriting keeps the same length while making that length easier to build on later.

Give the first, mention the second

Write the quadratic version, state that it is O(n squared), and say that an O(n log n) solution exists using a sorted list of best endings and a binary search.

If asked to implement it, it is the loop above with the two cases turned into an assignment and an append, and the answer is the list's final length. If not asked, you have already demonstrated that you know it exists, which is most of the credit.

Complexity· 5 min

Cost of the table version

Time and space for the quadratic longest-run version on n values.

Problem· 30 min

Longest Increasing Subsequence

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround