PROBLEM STATEMENT
You are given a list of integers, and you are allowed to group elements into pairs. Each element
must either belong to a single pair or remain unpaired. Sum the products of the pairs with the
values of the unpaired elements. Your goal is to maximize this sum.
For example, consider the list {0, 1, 2, 4, 3, 5}. If you make the pairs (2, 3) and (4, 5), the
sum is 0 + 1 + (2 * 3) + (4 * 5) = 27.
You are given a vector data containing the list of integers. Return the maximum possible sum.
DEFINITION
Class:CreatePairs
Method:maximalSum
Parameters:vector
Returns:int
Method signature:int maximalSum(vector data)
CONSTRAINTS
-data will contain between 1 and 50 elements, inclusive.
-Each element of data will be between -1000 and 1000, inclusive.
EXAMPLES
0)
{0, 1, 2, 4, 3, 5}
Returns: 27
The example from the problem statement.
1)
{-1, 1, 2, 3}
Returns: 6
If we create a pair (2, 3) we get the sum (-1) + 1 + (2 * 3) = 6.
2)
{-1}
Returns: -1
No pairs can be created, so the answer is -1.
3)
{-1, 0, 1}
Returns: 1
In this case we can create a pair (-1, 0) to make the sum equal to (-1) * 0 + 1 = 1.
4)
{1, 1}
Returns: 2
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.