TopCoder problem "BagsOfGold" used in SRM 228 (Division I Level Two)



Problem Statement

    My partner and I have bags of gold, lined up in a row. The bags are different sizes. My partner has offered to split up the gold using the following system: we take turns, each time choosing one bag from either end of the line. She has even generously offered to let me go first -- hmmmmmmmm....

I need software to tell me the total amount of gold that I will get compared to how much my partner will get if I choose first. Of course we will assume that my partner and I are brilliant and always choose in the optimum way.

Create a class BagsOfGold that contains a method netGain that is given a int[] bags, the values of all the bags of gold in the order in which they are lined up. It should return how much more gold I will get than my partner if we both behave optimally. (I fear that the answer might be a negative number since my partner proposed the plan.)

 

Definition

    
Class:BagsOfGold
Method:netGain
Parameters:int[]
Returns:int
Method signature:int netGain(int[] bags)
(be sure your method is public)
    
 

Constraints

-bags will contain between 1 and 50 elements inclusive.
-Each element of bags will be between 1 and 100,000 inclusive.
 

Examples

0)
    
{7,2}
Returns: 5
I will choose the 7, and then she gets the 2. So the result is 7 - 2 = 5.
1)
    
{2,7,3}
Returns: -2
It doesn't matter whether I choose the 2 or the 3. She will choose the 7 and I will get the remaining bag. (2+3) - 7 = -2
2)
    
{1000,1000,1000,1000,1000}
Returns: 1000
Since I choose first I will get 3 bags and my partner will get only 2 bags. They all have the same value so (1000+1000+1000) - (1000+1000) = 1000.
3)
    
{823,912,345,100000,867,222,991,3,40000}
Returns: -58111

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=3491

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6517&pm=3491

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Recursion