Statistics

Problem Statement for "MagicSubset"

Problem Statement

You are given n stones labeled from 0 to n-1. Each stone has an integer value: the value of stone i is value[i]. Note that some of those values may be negative or zero.

You would like to choose a subset of stones such that the sum of their values is maximized. (You are allowed to choose the empty subset. In that case, the sum of the values of the chosen stones is zero.)

This would be an easy problem, but there is a catch: the stone labeled 0 has magical properties. If you include this stone into your chosen subset, its entire sum is multiplied by -1. (The value of stone 0 still contributes to the sum. See Example 1.)

You are given the int[] value containing n elements: the values of your stones. Find and return the maximum sum of a subset of stones, given that the sum of any subset that contains stone 0 is negated.

Definition

Class:
MagicSubset
Method:
findBest
Parameters:
int[]
Returns:
int
Method signature:
int findBest(int[] values)
(be sure your method is public)

Notes

  • The value of n is not given explicitly. Instead, you can determine it as the number of elements in value."

Constraints

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

Examples

  1. {1,10,4,-6,3}

    Returns: 17

    There are five stones. The magic stone 0 has value 1. In this case, it is optimal to ignore the magic stone and to choose only the stones labeled 1, 2, and 4. The sum of their values is 10 + 4 + 3 = 17.

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

    Returns: 8

    In this case the optimal choice is to take the stones labeled 0, 1, and 3. The sum of their values is 3 + (-5) + (-6) = -8. However, since we included the magic stone 0, we have to multiply this sum by -1, getting the final value (-8) * (-1) = 8.

  3. {0,0,0,0,0,0,0,0,0}

    Returns: 0

    Stones can also have value 0.

  4. {-100}

    Returns: 100

  5. {100}

    Returns: 0

    In this case, we don't take any stones.

  6. {-3,1,-4,1,5,-9,2,6,-5,3,5}

    Returns: 23

  7. {43,20,-45,-49,4,20,5,20,-10,-38,11,-8,-11,32,-37,0,43,-5,-7,-15,-6,-24,9,-39,-42,-17,-40,-50,-46,-9,48,-42,-41,23,-32,50,29,9,6,12,50,47,40,-36,7,17}

    Returns: 606

  8. {-38,29,6,-13,26,-20,11,10,-20,21,3,30,44,-35,-18,19,-39,-35,-18,-14,14,-17,8,38,33,41,-16,40,25,20,20,-20,-47,10,38,5,-27}

    Returns: 491

  9. {-14,-42,29,34,17,34,7,-7,-20,-21,-50,9,-25,39,1,30,17,9,33,21,-21,-46,-39,37,-49,-9,47,33,41,10,-28,9,-5,3,-20,9}

    Returns: 469

  10. {14,40,50,-28,-11,19,-41,29,-46,-4,-47,14,-44,20,14,-43,-12,-2,-50}

    Returns: 314

  11. {43,8,-44,0,-19,10,19,-19,20,40,32,44,45,-22,22,37,9,37,11,25,-20,-42,45,19,7,-34,-38,31,12,46,10,14,45,27,-23,-39}

    Returns: 615

  12. {17,10,18,47,-36,39,-41,13,-15,-11,-16,50,33,40,-15,-5,18,-42,-1,-8,-30,-13,18}

    Returns: 286

  13. {-4,24,18,4,44,42,0,-11,-17,-35,39,40,14,-11,-50,-37,45,-5,27,39,-12,38,17,50,46,-21,-8,13,-15,-17,48,45,5,18,-13,-11,20,4,5,-24,-9,-10,-14}

    Returns: 645

  14. {-13,-46,40}

    Returns: 59

  15. {7}

    Returns: 0

  16. {4,10,-28,35,-47,15,-37,47,-48,9,-19,26,-14,-8,-9,-18,40,-50,-21,-32,-14,30}

    Returns: 341

  17. {-4,17,-47,-43,-47,-11,14,-35,-30,-5,-4,26,49,3,-22,-30,26,2,-41,40,-24,50}

    Returns: 343

  18. {12,6,46,20,22,-40,41,29,27,-22,-33,-6,-30,-11,-50,35,-39,14,38,32,-29,21,-3,-36,5,-33,50,18,-47,16,44,2,-15,-19,-1,25,-40,-17,-17,14,-34,-22,-43,31,28,-35,-36,22}

    Returns: 646

  19. {28,-20,-10,-16,5,-31,25,16,-19,10,21,21,-35,-38,-44,-1,28}

    Returns: 186

  20. {-44,-12,7}

    Returns: 56

  21. {31,-14,14,-30}

    Returns: 14

  22. {30,24,-17,1,45}

    Returns: 70

  23. {-50,5,50,3,39,39,43,-20,28,-8,-24,-28,-34,-5,47,44,38,9,-29,22,-11,19,48,21,-27,-9,-8,41,-8,41,-14,18,-41,42}

    Returns: 597

  24. {-9,37,23,39,-6,20,-12,-21,11,44,-19,-14,-3,8,14,-36,26,-23,-16,-20,34,23,-28,-4,0,27,1,-22,-37,44,-16,-14,-32,-42,-33}

    Returns: 407

  25. {13,42,-26,24,22,-9,-28,15,-48,-35,-10,-43,38,9,-10,-7,-11,-4,11,-41,-16,21,21,-31,-38,20,-44,2,33,41,-8,11,-48}

    Returns: 444

  26. {21,-21,-39,22,-45,-26,18,-32,26,41,38,-6,-19,9}

    Returns: 167

  27. {48,40,-3,-25,6,50,14,-22,-37,-2,-16,-41,27,-5,43,-41,30,47,-10,-3,19,-26,16,-14,-16,1,23,34,28,23,-22,-41,34,-43,5,-47,-30,39,39,-17,-41,44,45,-40,27,-14}

    Returns: 634

  28. {12,-17,-47,-29,-14,36,49,-19,-33,37,39,6,4,0,-16,-25,11,48,47,5,-1,-25,5,42,18,43,31,15,7,-2,-6,10,11,16,-41,12,46,-22,35,-17,43,10,10,19,-24,-42,10,25,41,31}

    Returns: 762

  29. {24,-17,16,3,-7,41,-31,-25,46,-41,-37,-2,3,-17,14,-4,12,29,-38,-29,-26,45,-25,0,-46,49,-21,15,1,34,48,13,33,-25,20,40,44,-29,-1,-49}

    Returns: 506

  30. {-27,38,41,36,19,43,32,-50,18,9,31,-40,-44,48,10,33,16,-3,-26,27,-3,-27,20,-5,36,-28,-36,-45,0,-41,45,-25,27,44,48,-35,17,-9,-47,-8,-18,33,-30,-1,-14}

    Returns: 671

  31. {-38,4,34,32,37,-30,-13,-37,27,43,36,-38,-26,41,-22,35,49,46,-17,14,-41,-44,8,24,-35,6,36,-45,38,16,-30,-49,13,-5,-28,19,9,1,12,-41,19,21,5,10,18,-17,-6,43,50,-6}

    Returns: 746

  32. {-12,-30,49,44,-27,-26,48,29,-30,43,19,-8,7,9,41,10,2,-1,-11,-37,35,13,6,-44,34,42,44,-32,-36,20,18,14,40,-30,-8,20,-23,-29,6,-22,-41}

    Returns: 593

  33. {-43,10,-40,17,-16,7,-47,-48,35,7,-21,-8,32,47,11,-34,-25,-4,-31,17,30,-16,19,2,35,40,25,26,-13,47,-39,-42,6,-47,33,-48,-4,-5,36,-34,27,2}

    Returns: 565

  34. {-8,2,-10,-24,-33,-29,-16,0,35,48,-2,15,13,16,36,-42,25,-14,-22,19,-11,34,-14,-22,-41,46,-50,28,43,20,45,-2,44,-2,5,29,-44,-16,8,-49,36,21,-29,-18,-34,-47,-46}

    Returns: 625

  35. {30,15,-27,4,46,-12,42,-21,-20,30,38,-6,-23,-45,5,-40,22,-4,37,32,-46,-29,-29,35,3,47,-14,17,49,-4,17,10,-15,-5,-32,-42,-15,13,49,-15,-47,-17,16}

    Returns: 527

  36. {22,15,-38,4,-23,-44,-29,-27,39,-5,-9,-16,2,-44,28,-45,-27,-50,-6,45,25,26,-47,-24,-29,-1,48,2,11,-35,24,-3,-24,-27,35,19,-5,28,-9,47,19,10,-22}

    Returns: 567

  37. {-100, 1 }

    Returns: 100

  38. {3, -5, 1, -6 }

    Returns: 8

  39. {100, -1 }

    Returns: 0

  40. {1, 10, 4, -6, 3 }

    Returns: 17

  41. {-10, 2, -20 }

    Returns: 30

  42. {10, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 2, 5, 7, 8, 2, 10, -1, -42, 13, 41, 1, 1, 1, 1, 1, 3, 5, -24, 4, 1, 5, 2, 4, 4, 6, 8, 9, 4, 2, 6, 7, 9, 1 }

    Returns: 190

  43. {100, 1, 1 }

    Returns: 2

  44. {5, 5 }

    Returns: 5

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

    Returns: 6

  46. {-100, -10, -10 }

    Returns: 120

  47. {-38, 76, 4, 79, -26, -23, 6, -73, 92, -44, 13, -38, -39, -100, 6, 86, -66, -71, 82, -100, -29, 84, 65, -40, -48, 97, -22, 10, -67, 86, -76, -32, -9, 83, -30, 70, 61, -76, -40, -32, -26, -61, -88, 89, -31, 57, -91, 80, 66, 95 }

    Returns: 1416

  48. {0, -4, -3, -44, 1 }

    Returns: 51

  49. {-100 }

    Returns: 100

  50. {1, 10, -5 }

    Returns: 10

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: