# Teaching Kids Programming – K Items With the Maximum Sum

Teaching Kids Programming – K Items With the Maximum Sum | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it. You are given four non-negative integers numOnes, numZeros, numNegOnes, and k.

The bag initially contains:
numOnes items with 1s written on them.
numZeroes items with 0s written on them.
numNegOnes items with -1s written on them.
We want to pick exactly k items among the available items. Return the maximum possible sum of numbers written on the items.

Example 1:
Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 2
Output: 2
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 2 items with 1 written on them and get a sum in a total of 2.
It can be proven that 2 is the maximum possible sum.

Example 2:
Input: numOnes = 3, numZeros = 2, numNegOnes = 0, k = 4
Output: 3
Explanation: We have a bag of items with numbers written on them {1, 1, 1, 0, 0}. We take 3 items with 1 written on them, and 1 item with 0 written on it, and get a sum in a total of 3.
It can be proven that 3 is the maximum possible sum.

Constraints:
0 <= numOnes, numZeros, numNegOnes <= 50
0 <= k <= numOnes + numZeros + numNegOnes

### Teaching Kids Programming – K Items With the Maximum Sum

We can construct the sorted array, and then pick the K items exactly from the right to the left. This has the time complexity of O(N) where N is the total number (equals to Ones + Zeros + Negative-Ones). And the space complexity is also O(N) as we need to prepare such an array.

 ```1 2 3 4 5 6 ``` ```class Solution:     def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:         if k == 0:             return 0         a = numNegOnes * [-1] + numZeros * [0] + numOnes * [1]                 return sum(a[-k:])```
```class Solution:
def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
if k == 0:
return 0
a = numNegOnes * [-1] + numZeros * [0] + numOnes * [1]
return sum(a[-k:])```

A special case is when K is zero, we return 0, otherwise we use the list comprehension to return the sum of the last K numbers of the constructed sorted array (that contains numNegOnes -1, numZeros 0, and numOnes 1).

A faster approach/algorithm would be to compute the ones we have (as we pick them first), then subtract the negative ones which is max(0, k-numZeros-numOnes). If k is exceeding the amount of zeros plus ones, then we have to minus the amount of negative ones. The time/space complexity is O(1) constant.

 ```1 2 3 ``` ```class Solution:     def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:         return min(k, numOnes) - max(0, k - numZeros - numOnes)```
```class Solution:
def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int:
return min(k, numOnes) - max(0, k - numZeros - numOnes)```

GD Star Rating

545 words
Last Post: Introduction to Ledger Virtual Crypto Card

Source: Internet

We are offering free coding tuts

X