"The best that ends here"

Choosing what a box means is half the work. "The best answer among the first i elements" is often not enough to work out the next box; "the best answer that ends exactly at i" is. For the largest sum of a contiguous run the question is: does the best run ending at i extend the one before, or start afresh at i?

1here = best = values[0]
2for v in values[1:]:
3    here = max(v, here + v)
4    best = max(best, here)
5return best

here is the best total that ends exactly at this element: once the earlier total has gone negative there is no point carrying it, so you start again. The real answer is the largest of all the here values, not the last one.

Counting follows the same pattern. Counting how many ways a string of digits can be read as letters, the box becomes "how many readings the first i digits have"; if the last digit is a letter on its own the box before is added, and if the last two digits together are a letter the box two before is added.

Tasks