UVa 10891

From Algorithmist
Jump to navigation Jump to search

10891 - Game of Sum[edit]

Summary[edit]

This is a variation of a classic Dynamic Programming problem, only in this one, you can take any number of numbers from either end.

Explanation[edit]

In the classic problem, the recurrence is:

Now we just add an iteration over it:

And the corresponding recursive memoization is trivial to implement.

Implementations[edit]

Input[edit]

4
4 -10 -20 7
4
1 2 3 4
6
1 1 1 1 1 1
5
-1 0 0 0 5

Output[edit]

7
10
6
6