Choose Exactly k Ones, Zeros, and Negative Ones for the Greatest Sum
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
A bag contains numOnes entries equal to 1, numZeros entries equal to 0, and numNegOnes entries equal to -1. Choose exactly k available entries and return the largest possible sum.
```cpp
class Solution {
public:
int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k);
};
```
### Examples
**Example 1:**
```text
Input: numOnes = 2, numZeros = 1, numNegOnes = 3, k = 5
Output: 0
Explanation: Choose both ones, the zero, and two negative ones: 2+0-2=0.
```
**Example 2:**
```text
Input: numOnes = 0, numZeros = 2, numNegOnes = 1, k = 0
Output: 0
Explanation: Choosing no entries gives a sum of zero.
```
### Constraints
- `0 <= numOnes, numZeros, numNegOnes <= 50`.
- `0 <= k <= numOnes+numZeros+numNegOnes`.
### Clarifying Questions
- Must exactly k items be chosen? Yes, even if some choices are negative.
- Can k be zero? Yes; the empty selection sums to zero.
- Is there always enough supply? Yes; k is at most the total item count.
- Can the best answer be negative? Yes.
```hint Check the boundary
Check a case where exactly k choices force you to include negative ones.
```
Overview: Choose exactly k available items valued one, zero or negative one to maximize their sum, including any forced negative selections.