Problem Statement
Elly has N integers, given in the int[] numbers. She also has N-1 signs. Each of the signs is either a plus ('+') or a minus ('-'). The girl has numPluses plus signs and numMinuses minus signs. It is guaranteed that numPluses + numMinuses equals N-1.
Elly wants to place her numbers in a sequence and then put a single sign between each pair of integers. She can put the signs and the numbers in any order. Now the girl wonders what is the maximal value she can get after putting the signs and evaluating the expression. Help her by finding the resulting value.
Definition
- Class:
- EllysExpression
- Method:
- getMax
- Parameters:
- int[], int, int
- Returns:
- int
- Method signature:
- int getMax(int[] numbers, int numPluses, int numMinuses)
- (be sure your method is public)
Constraints
- numbers will contain between 1 and 50 elements, inclusive.
- Each element of numbers will be between -1000 and 1000, inclusive.
- numPluses will be between 0 and the number of elements in numbers minus one, inclusive.
- numMinuses will be between 0 and the number of elements in numbers minus one, inclusive.
- numPluses plus numMinuses will be exactly one less than the number of elements in numbers.
Examples
{-6, 11, -13, 17, 5}1
3
Returns: 42
Here the best we can get is 11 - (-6) - (-13) + 17 - 5 = 42.{666}0
0
Returns: 666
With a single number there are no signs and the expression is evaluated to that number.{100, 200}0
1
Returns: 100
It's better to swap the numbers, since 200 - 100 > 100 - 200.{466, 103, -687, 350, 446, 344, 777, 889, 650, 172, -716, -608, -191, -731, 168, 871, 410, 703, 68, 270, 598, -446, 907, 861, -92, 387, 182, -41, 173, 183, 369, 533, 522, 746, 300, 24, 924, 488, 631, 539, 636, 936, 906, -337, 737, 470, 556, 148}6
41
Returns: -3006