Statistics

Problem Statement for "CreatePairs"

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 int[] data containing the list of integers. Return the maximum possible sum.

Definition

Class:
CreatePairs
Method:
maximalSum
Parameters:
int[]
Returns:
int
Method signature:
int maximalSum(int[] data)
(be sure your method is public)

Constraints

  • data will contain between 1 and 50 elements, inclusive.
  • Each element of data will be between -1000 and 1000, inclusive.

Examples

  1. {0, 1, 2, 4, 3, 5}

    Returns: 27

    The example from the problem statement.

  2. {-1, 1, 2, 3}

    Returns: 6

    If we create a pair (2, 3) we get the sum (-1) + 1 + (2 * 3) = 6.

  3. {-1}

    Returns: -1

    No pairs can be created, so the answer is -1.

  4. {-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.

  5. {0}

    Returns: 0

  6. {0, 0}

    Returns: 0

  7. {2, 2}

    Returns: 4

  8. {-2, -2}

    Returns: 4

  9. {-2, 2}

    Returns: 0

  10. {-1000}

    Returns: -1000

  11. {1000}

    Returns: 1000

  12. {-1000, -1000, 1000, 1000}

    Returns: 2000000

  13. {-1000, 1000}

    Returns: 0

  14. {1}

    Returns: 1

  15. {2}

    Returns: 2

  16. {1, 1}

    Returns: 2

  17. {1, 2}

    Returns: 3

  18. {2, 3}

    Returns: 6

  19. {1, 1, 1}

    Returns: 3

  20. {1, 1, 2}

    Returns: 4

  21. {1, 2, 3}

    Returns: 7

  22. {2, 3, 4}

    Returns: 14

  23. {0, 1}

    Returns: 1

  24. {0, 2}

    Returns: 2

  25. {0, 1, 1}

    Returns: 2

  26. {0, 1, 2}

    Returns: 3

  27. {0, 2, 3}

    Returns: 6

  28. {0, 1, 1, 1}

    Returns: 3

  29. {0, 1, 1, 2}

    Returns: 4

  30. {0, 1, 2, 3}

    Returns: 7

  31. {0, 2, 3, 4}

    Returns: 14

  32. {-1}

    Returns: -1

  33. {-2}

    Returns: -2

  34. {-1, -1}

    Returns: 1

  35. {-1, -2}

    Returns: 2

  36. {-2, -3}

    Returns: 6

  37. {-1, -1, -1}

    Returns: 0

  38. {-1, -1, -2}

    Returns: 1

  39. {-1, -2, -3}

    Returns: 5

  40. {-2, -3, -4}

    Returns: 10

  41. {0, -1}

    Returns: 0

  42. {0, -2}

    Returns: 0

  43. {0, -1, -1}

    Returns: 1

  44. {0, -1, -2}

    Returns: 2

  45. {0, -2, -3}

    Returns: 6

  46. {0, -1, -1, -1}

    Returns: 1

  47. {0, -1, -1, -2}

    Returns: 2

  48. {0, -1, -2, -3}

    Returns: 6

  49. {0, -2, -3, -4}

    Returns: 12

  50. {-1, 1}

    Returns: 0

  51. {-2, 2}

    Returns: 0

  52. {-1, -1, 1, 1}

    Returns: 3

  53. {-1, -2, 1, 2}

    Returns: 5

  54. {-2, -3, 2, 3}

    Returns: 12

  55. {-1, -1, -1, 1, 1, 1}

    Returns: 3

  56. {-1, -1, -2, 1, 1, 2}

    Returns: 5

  57. {-1, -2, -3, 1, 2, 3}

    Returns: 12

  58. {-2, -3, -4, 2, 3, 4}

    Returns: 24

  59. {-1, 0, 1}

    Returns: 1

  60. {-2, 0, 2}

    Returns: 2

  61. {-1, -1, 0, 1, 1}

    Returns: 3

  62. {-1, -2, 0, 1, 2}

    Returns: 5

  63. {-2, -3, 0, 2, 3}

    Returns: 12

  64. {-1, -1, -1, 0, 1, 1, 1}

    Returns: 4

  65. {-1, -1, -2, 0, 1, 1, 2}

    Returns: 6

  66. {-1, -2, -3, 0, 1, 2, 3}

    Returns: 13

  67. {-2, -3, -4, 0, 2, 3, 4}

    Returns: 26

  68. {-614, -17, 662, 202, -398, 397, 325, -830, -885, 253, -221, 905, 15, -488, -131, 308, -259, -553, 842, -445, -631, -40, 321, 833, -300, -106, 247, -65, -387, 693, 517, -692, -339, 223, -477}

    Returns: 4183022

  69. {365, 143, 323, -450, -817, 626, -350, -405, 629, 799, -502, 982, 490, -254, -519, 281}

    Returns: 2239547

  70. {-600, 697, -384, -630, -810, 311, 466, 806, 767, 584, -343, -788, -335, 553, 657, 840}

    Returns: 3000993

  71. {-912, -262, 147, 737, 553, -865, -66}

    Returns: 1213880

  72. {768, -233, -669, 219, -482, 623, -879, 615, 306, 416, 352, -815, 578, -422, 732, -373, 137, -780, -254, 606}

    Returns: 3045290

  73. {112, -13, 262, 188, -686, 658, -393, 339, 530, -287, -889, -248, 782, -383, -637, 187, 504, 180, -883, -518, 641, 439, 601, -584, 859}

    Returns: 3523599

  74. {392, -484, -556, -748, 743, -980, -1, 553, 669, -281, 517, 653, 664, 892, 944, 530, -626, 56, -196, 977, -919, -246, 999, 946, -667, -913, 356}

    Returns: 6090258

  75. {568, -777, 47, 265, 85, 592, -566, 5, -818, -11, -528, -939, 838, 309, 239, -653, -262, 123, -306, -269, -959, 816, 265, -679, 685, -486, 341, -665, 589, 516, 284, -484, 622, 428, -959, -438, -365, 766, -49, 554, 439, 186, 844}

    Returns: 6446049

  76. {52, -881, 29, -760, -931, -21, 257, -558, 498, 699, -748, 846, 887, -203, -80, -955, -880, -308, -198, 501, 706}

    Returns: 3953390

  77. {-106, 978, -119, 972, -590, -267, 429, -44, -420, 914, 499, -160, 95}

    Returns: 1750547

  78. {-696, 436, 265, 573, 32, -94, -487, 22, -191, -39, 283, -446, 70, -926, 943, 584, -834, 907, 816, 307, -435, -327, -115, 659, 479, 675, 307, 214}

    Returns: 3723603

  79. {694, -703, -983, -507, -499, -496, 810}

    Returns: 1505686

  80. {165, -552, -392, 982, 397, -871, 121, -516, -349, 398, -37, 760, -805, 172, 132, -664, 869, -895, 727, -681, 746, 802}

    Returns: 4117041

  81. {379, 435, -846, 303, -907, -786, -80, 625, 25, 740}

    Returns: 1465142

  82. {640, -663, 526}

    Returns: 335977

  83. {-213, 317, 941, -487, 124, 646, 913, 485}

    Returns: 1315482

  84. {-251, 83, 457, -386, -912, -393, 3, -187, 718, 347, -159, -409, -30, -355, -388, -730, 595, 421, 223, 435, -783}

    Returns: 2144491

  85. {867, -626, 429, 993, 292, -173, 393, 645, 433, -507, -733, 375, 980, -721, -672, -272, 1, 758, 106, 248, 189, -216, 392, 895, 837, 778, -535, -466, 147, 594, 368, 706, 942, -515, 586, 391, -608, -881, -28, -994, 851, 95, 257, 335, -626, -36}

    Returns: 7818754

  86. {609, 47, -806, -738, 484, -317, -932, -963, -906, 8, -37, 456, -67, -88, 996, -57, 756, -128, 506, 461, 247, 130, -675, -234, 649, 730, -676, 994, 82, -7, 187, 431, 779, 545, -99, -187, -66, 469, 911, 988, 411, -306, 420, -705, -995, 200, -196, 501, 499, -861}

    Returns: 8097821

  87. {633, 206, 477, -948, 559, 249, -784, -334, -344, -730, 847, 753, -589, -199, -945, -567, 290, 8, -655, 58, -267, -964, 621, 526, -384, -332, -651, -540, 8, 512, -615, -284, 586, 443, -942, 190, -458, 519, -385, 389, 333}

    Returns: 6173096

  88. {-398, 745, -900}

    Returns: 358945

  89. {296, 128, 130, 647, -233, 540, -832, -802, -331, -561, 959, 371, -646, 691, -164, 404, 403, -418, 713, -336, -839, -94, 316, 201, -615, -460, -985, 233, -417, -474, 74, -192}

    Returns: 4253392

  90. {105, -321, 323, -152, -334, -406, -846, -122, -901, 770, -908, -132, 499, 763, 815, -854, -292, 310, -891, 725, 654, 884, 66, 143, -50, -396, 968, -232, 746}

    Returns: 4938859

  91. {-928, -378, -736, 188, 41, 355, 29, -281, -807, 440, 226, 400, -654, 196, 173, 973, -582, -278, -617, -419, 546, 344, 163, -343, 922, -340, -770, -97, -937, 793, 330, -796, -248}

    Returns: 4789065

  92. {-713, -187, -666, 713, -499, 657, -364, 707, 320, -892, 174, -697, -719, 57, 915, -604, -319, -362, 276, -727, -552, -547, -399, -135, -227, -375, -171, 950, 487, -458, 563, -613, -364, -383, 271, -998, -764, -72, 833, 184, -334, 60, 150, -192, -328, -990, -960, 589, -545}

    Returns: 7621446

  93. {-871, -579, 805, -506, 973, 843, 752, 388, 104, 185, -293, -474, -744, -487, -445, -429, -554, -38, -330, -541, -835, 535, -672, 327, -621, -12, -523, 239, 559, 876, -662, -924, 472, -648, -193, -590, -66, 835}

    Returns: 6452112

  94. {-285, 259, 104, 762, 763, 612, 957, 69, 550, -10, 984, 519, -417, -951, -422, -850, 885, -502, -226, -893, -451, -732, 991, -253, -790, 195, 288, -687, -762}

    Returns: 5736984

  95. {237, 616, -964, 196, -32, 704, 264, 444, 529, -16, 336}

    Returns: 834528

  96. {116, 780, -962, 930, -710, -239, 618, -326, 757, -744, 159, -5, 823, 879, -368}

    Returns: 3000597

  97. {107, -539, -580, 375, -397, -244, -309, -652, 692, 866, 450, -406, 196, -111, -384, 354, 67, 733, 971, -719, -199, 568, 316, 607, 179, 899, 689, 600, -581, 712, -17, -979, -657, -328, 804, -193, -356, -162, 920, 682, 851, 864, -857, -63}

    Returns: 7281612

  98. {152, -14, -913}

    Returns: 12934

  99. {-62, 932, 613, -600, -241, 675, 526, 944, -711, -833, -28, 981, -996, 810, 569, -815, 646, 643, 735, -776, -57, -128, 691, 672, 594, -423, 381, -530, 924, -54}

    Returns: 6364462

  100. {527}

    Returns: 527

  101. {878, -538, 531, 306, 297, -807}

    Returns: 991266

  102. {-34, -972, 33, 865, -701, -433, -612, -519, 363, 600, 212, -633, -68, -396, -598, 42}

    Returns: 2150252

  103. {388, 861, 794, 135, 904, -75, -272, 753, -826, 401, -207, -41, -309, -98, 382, 746, -888, -264, -414, 918, 616, 29, 734, 90, 742, -677, -749, 447, -924, 376, 503}

    Returns: 5176022

  104. {-380, 347, -355, -502, -829, 131, -868, -111, 592, 28, -55, -747, -728, -525, -861, -271, -333, -934, 818, 963, -779, -426, 100, 369, -460, -812, 211, 911, -842, 700, -748, -643}

    Returns: 5968632

  105. {837, -226, 508, -30, 481, 728, -670, 306, 979, -103, -499, -640, 269, -594, -705, 345, -963, -617, 318, -445, -365, -604, -973, -123, 954, -264, -471, 623, 997, -857, 603, 553, -637, 85, 439, -577, 353, -844, -955, -101, -84, 721, 799, 184}

    Returns: 7911512

  106. {363, 108, 206, -303, -733, -349, 699, 359, -905, -828, -963, -202, -525, -712, 151, -584, 689, -720, -628, -12, 640, 348, 565, -342, -282, 280, -639, -467, -361, 23}

    Returns: 4179344

  107. {593, 850, -892, -286, 124, -391, -593, 636, 418, 323, -809, 714, 934, -768, -45, 330, -356, 54, 973, 851, -195, 656}

    Returns: 4027683

  108. {1, 1}

    Returns: 2

  109. {-1000, -1, -2, 1, 2, 3 }

    Returns: 2006

  110. {-10, -9, 0 }

    Returns: 90

  111. {1 }

    Returns: 1

  112. {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 25000000

  113. {3, 2, -1, -2, -3 }

    Returns: 11

  114. {-3, -2, -1, 0, 1, 2, 3 }

    Returns: 13

  115. {1, 2 }

    Returns: 3

  116. {-1, -1, 0 }

    Returns: 1

  117. {-1, -1, -1, -1, -5 }

    Returns: 5

  118. {-5, -4, -3, -3, -2, -2, 0, 1, 1, 1, 3, 4 }

    Returns: 48

  119. {4, 4, -1, -4, -4 }

    Returns: 31

  120. {-1 }

    Returns: -1

  121. {1, 1, 0, -5, -6, -7 }

    Returns: 44

  122. {-2, -1, 0 }

    Returns: 2

  123. {-3, -2, -1 }

    Returns: 5

  124. {-5, 0, -1 }

    Returns: 5

  125. {-1, -1, -1 }

    Returns: 0

  126. {-5, -3, -2, -2 }

    Returns: 19

  127. {3, 3, 3, 3 }

    Returns: 18

  128. {1, 1, 1, 1, 1, 1, 1, 2, -2, -1, 0, -3, -5, -8 }

    Returns: 55

  129. {1, 1, 1, 1, 1, 1, 1, 2, -2, -1, 0 }

    Returns: 11

  130. {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: 21451

  131. {-4, -3, -2, 3, 4 }

    Returns: 22

  132. {1, 0, 1, -1, 2, 3, -2, 2, -7 }

    Returns: 24

  133. {-1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000, -1000 }

    Returns: 25000000

  134. {2, 3, -5, 5 }

    Returns: 12

  135. {-4, 3, 3 }

    Returns: 5

  136. {1, 1, -999, -1000, 1000, -5, -7, -9, 0, 1, -1, -1, -1 }

    Returns: 1000072

  137. {-2, -1, -1 }

    Returns: 1

  138. {-5, -5, -1, 0, 5 }

    Returns: 30

  139. {-1, -2, -3, 0, 0, 0, 1, 1, 3 }

    Returns: 11

  140. {-1, -2, -3, 0, 0, 0, 1, 1, 3, -1, -3, -6, 8, 9, -9, 12, 11, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 7, 6 }

    Returns: 417

  141. {-1, -2, -3, 0, 0, 0, 1, 1, 3, -1, -3, -6, 8, 9, -9, 12, 11, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1 }

    Returns: 375

  142. {0, 9, 0, -3, -9 }

    Returns: 36

  143. {1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 9

  144. {-1, 0 }

    Returns: 0

  145. {-50, -2, -1, -1, 1000, 1, 1, -100 }

    Returns: 6003

  146. {-5, -1, 0 }

    Returns: 5

  147. {-10, -15 }

    Returns: 150

  148. {-400, -500, -900, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 999, 999 }

    Returns: 1448011

  149. {2, 3, 10 }

    Returns: 32

  150. {-1, 0, 1, -2, -3, 0 }

    Returns: 7

  151. {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, 421 }

    Returns: 27101

  152. {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, 421, 422, 423, 424, 425, 0, -1, 1 }

    Returns: 385808

  153. {1, 8 }

    Returns: 9

  154. {-5, -5 }

    Returns: 25

  155. {34, 45, 676, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, -34, -1, -1, -1, -1, -454, -22, -33, -1, -1 }

    Returns: 46623

  156. {43, 34, 1, 1, 0, 0, 0, 0, -123, -456, -1, -1 }

    Returns: 57553

  157. {-1000, -1000, 0 }

    Returns: 1000000

  158. {-1000, -1000 }

    Returns: 1000000

  159. {-40, -30, 0 }

    Returns: 1200

  160. {4, 5, 6 }

    Returns: 34

  161. {5, 6, 7 }

    Returns: 47

  162. {0, 5, -5, -8, 3, -7, 5, -2 }

    Returns: 94

  163. {-2, -3, -4 }

    Returns: 10

  164. {-5, -4, -1 }

    Returns: 19

  165. {1, 3 }

    Returns: 4

  166. {-2 }

    Returns: -2

  167. {-2, 0 }

    Returns: 0

  168. {-6, -5, -3, -2, 0 }

    Returns: 36

  169. {1, 3, 5 }

    Returns: 16

  170. {-1, 3, 3 }

    Returns: 8

  171. {1, 1, 1 }

    Returns: 3

  172. {-1, 0, 1 }

    Returns: 1

  173. {-1, 1, 1 }

    Returns: 1

  174. {3, 3 }

    Returns: 9

  175. {-5, -10, 8 }

    Returns: 58

  176. {-100, -50, -50 }

    Returns: 4950

  177. {-1, -1 }

    Returns: 1

  178. {0, -1, 0, -1, -1 }

    Returns: 1

  179. {-10, -20, -30 }

    Returns: 590

  180. {-5, -1, 2, 4, 5 }

    Returns: 27

  181. {-100, -20, -23, -57, 0, 2, 43, 53, 87, 255 }

    Returns: 30626

  182. {0, -1, 0 }

    Returns: 0

  183. {0, -1, 0, -1 }

    Returns: 1

  184. {-3, -2, -1, 0 }

    Returns: 6

  185. {-2, 1, -3, 0, 1, 2, 3 }

    Returns: 14

  186. {-5, 1, 2, 4 }

    Returns: 4

  187. {1, 1, 1, 2, 2, 2 }

    Returns: 9

  188. {-4, -3, -2, -1, 1, 2, 3 }

    Returns: 21

  189. {5, 4, 3 }

    Returns: 23

  190. {0, -1, -1, -1, -1, -1 }

    Returns: 2

  191. {-2, -1, -1, 2, 3 }

    Returns: 7

  192. {1, 2, 3 }

    Returns: 7

  193. {1, 1, 4, 0, 0, 0, -1, 1, -2, -1, 0 }

    Returns: 9

  194. {44, -5, 55, -5, 1 }

    Returns: 2446

  195. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 10

  196. {0, 0, 0, 0, 1 }

    Returns: 1

  197. {1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2 }

    Returns: 16

  198. {-3, -2, -1, 2, 3 }

    Returns: 11

  199. {-7, -6, -5, 0, 1, 2, 3, 5, 6 }

    Returns: 79

  200. {3, 2, 1, 0, -1 }

    Returns: 7

  201. {0, -1, -2 }

    Returns: 2

  202. {-5, -5, 0, 0 }

    Returns: 25

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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: