TopCoder Statistics - Problem Statement

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

{7,2}

Returns: 5

I will choose the 7, and then she gets the 2. So the result is 7 - 2 = 5.
{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
{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.
{823,912,345,100000,867,222,991,3,40000}

Returns: -58111
{23,35,12,100000,99234,86123,3245}

Returns: -83644
{23,35,12,100000,99234,86123,3245,1}

Returns: 83645
{7,7,7,7,7,7,80,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7}

Returns: -66
{7,7,7,7,7,7,7,80,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7}

Returns: 73
{91,56,23,45,87,65,45,45,78,23,20,41,17,54,51,51,94,62,74,42,76,76}

Returns: 96
{92834,95461,15911,56189,6369,80545,31811,51263, 30076,68867,36905,32499,59799,334,82991,46636,98741,66601}

Returns: 42958
{129}

Returns: 129
{35463,88121,4362,94457,86235,83680,72686,6003,93069,2015,10436, 2139,93162,30380,19067,76335,78941,48620,55887,15679}

Returns: 101879
{19335,97643,11468,86267,79718,59584,12129,52642,86575,62307, 11545,52658,72377,39986,74850,1992,86928}

Returns: 1846
{91883,97793,54567,64714,98624}

Returns: 82567
{98473,41866,71129,65936,42626,9194,46718,96921,45613,47677,8763,54634, 47259,71448,9918,22666,32711,21692,40207,2017,23040,86083,77809,15472, 30718,39085,87911,54827,41686,28354,37203,6548,74184,3043,43961,95189, 1238,22002,93507,63546,32527,42778,31614}

Returns: -14953
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

Returns: 25
{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Returns: 0
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 11, 11, 11, 11, 111, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 112, 312, 312, 123, 123, 123, 123, 123, 123, 123, 123, 123, 123, 123, 123, 123, 123, 231, 31, 312 }

Returns: 316
{ 1234, 1233, 12, 312, 32, 23, 434, 12, 312, 45, 1234, 1233, 12, 312, 32, 23, 434, 12, 312, 45, 1234, 1233, 12, 312, 32, 23, 434, 12, 312, 45, 1234, 1233, 12, 312, 32, 23, 434, 12, 312, 45, 1234, 1233, 12, 312, 32, 23, 434, 12, 312, 45 }

Returns: 1995
{ 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3 }

Returns: 1
{ 9, 100, 1, 8 }

Returns: 98
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 66, 5, 4, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 6, 5, 4, 5, 6, 3, 4, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6 }

Returns: 68
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 1, 2, 3, 4, 65, 67, 2, 3, 4, 7, 2, 3, 4, 6, 6, 7, 2, 3, 4, 7, 78, 8, 82, 2, 3, 4, 7, 2, 2, 34, 4, 6, 7, 3, 2 }

Returns: 128
{ 100, 10, 10 }

Returns: 100
{ 1 }

Returns: 1
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 4, 3, 5, 4, 6, 7, 5, 6, 10, 2, 5, 4, 3, 4, 5, 6, 7, 9, 10 }

Returns: 28
{ 6, 4, 3, 5, 8, 8 }

Returns: 2
{ 1, 5, 20, 2, 1 }

Returns: -13
{ 1, 2, 3, 4, 5, 6, 6, 7, 8, 767, 765, 111, 76576, 5, 64, 654, 64, 7, 7657, 76575, 64, 65, 6454, 64, 654, 65464, 7, 5435, 65, 746, 7, 546, 7, 654, 7, 5435, 547, 6, 6, 7, 6547, 7654, 6, 754, 54353, 65, 7, 8 }

Returns: 118231

Statistics

Problem Statement for "BagsOfGold"

Problem Statement

Definition

Constraints

Examples