Show problems as
Classic problem #2600EasyMathGreedy

K Items With the Maximum Sum

Real-world version: Best Handful From the Token Tin
Tracked in this browser only
Read K Items With the Maximum Sum on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tin holds numOnes tokens marked 1, numZeros marked 0 and numNegOnes marked -1.

Take exactly k tokens out of the tin. Return the largest total the marks on those tokens can come to.

Examples

Example 1

Input
numOnes = 7, numZeros = 4, numNegOnes = 6, k = 13
Output
5

Taking all seven ones and all four zeros accounts for eleven tokens, so the last two must be negatives, giving 7 less 2.

Example 2

Input
numOnes = 3, numZeros = 4, numNegOnes = 0, k = 5
Output
3

All three ones fit and the remaining two tokens are zeros, so nothing pulls the total down.

Example 3

Input
numOnes = 0, numZeros = 0, numNegOnes = 9, k = 9
Output
-9

The tin holds nothing but negatives and all nine must come out.

Constraints

  • 0 <= numOnes <= 50
  • 0 <= numZeros <= 50
  • 0 <= numNegOnes <= 50
  • 0 <= k <= numOnes + numZeros + numNegOnes

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def k_items_with_maximum_sum(numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
Java
public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k)

More on the same topics