# UVA Problem: Game of Sum(10891)

**Problem Explanation:**

This Problem is classic example of dynamic programing.

Lets , Sum{i,j}= sum of element from i to j;

Best{i,j}= max point can be achieved from i to j element.suppose n=4, A can take following 7 way-

1. Sum{1} – Best{2-4}

2. Sum{1-2} – Best {3-4}

3. Sum{1-3} – Best {4}

4. Sum{1-4} – Best {}

5. Sum{4-4} – Best {1-3}

6. Sum{3,4} – Best {1-2}

7. Sum{2-4} – Best{1-1}A will choose from above 7 option in which he can get maximum score that

is Best[1-4].if A take {1} then B will get element{2-4}. Then B will play perfectly

to achieve more point from elemenmt {2-4}, which is Best{2-4}. B can achieve

Best{2,4} by maximum of following way-1. Sum{2} – Best{3-4}

2. Sum{2-3} – best{4}

3. Sum{2-4} – Best{}

4. Sum{4-4} – Best{2-3}B will take the option where he can get maximum score. If B take {2} , then

A will get element{3-4}, So A will try to get maximum score from element {3,4},

which is Best{3,4} and can be achieved either following way-1. Sum{3-3} – Best{4-4}

2. Sum{3-4} – Best{}

3. Sum{4-4} – Best{3-3}.Above we solved all the subproblems to calcualte option 1 of Problem Best[1-4],

Sum{1} – Best{2-4}. Similary we have to calculate other 6 option. And the option

with higest value is the our answer.