EllysExpression
Rookie SRM 9 · 2022-01-21 · by espr1t
Problem Statement
Elly has N integers, given in the
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.
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.
{-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.
{75, 99, 81, 7, -97, -85, 77, -94, 31, 61, -52, -99, -96, -36, 25, 10, -17, -56, -20, 79}
7
12
Returns: 1163
{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
Submissions are judged against all 113 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysExpression with a public method int getMax(vector<int> numbers, int numPluses, int numMinuses) · 113 test cases · 2 s / 256 MB per case