# K Items With the Maximum Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/k-items-with-the-maximum-sum)
Canonical: https://scaleengineer.com/dsa/problems/k-items-with-the-maximum-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
---
## Problem
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 `1`s written on them.
* `numZeroes` items with `0`s written on them.
* `numNegOnes` items with `-1`s 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`

# Approaches
## Simulation by Building a List
This approach simulates the problem by creating a list of all available items, already in descending order of value, and then summing up the first `k` items.
**Time:** O(N), where N is the total number of items (`numOnes + numZeros + numNegOnes`). Creating the list takes O(N) time. Summing the first `k` elements takes O(k) time. Since `k <= N`, the total time is dominated by list creation, making it O(N). · **Space:** O(N), where N is the total number of items (`numOnes + numZeros + numNegOnes`). We need to store all N items in a list.
**Pros:** Very intuitive and easy to understand.; Directly models the problem statement.
**Cons:** Inefficient in terms of both time and space.; Unnecessary creation of a large data structure for a simple problem.
### Explanation
To find the maximum sum, we should always pick items with the highest value first. The values available are 1, 0, and -1.

This method involves constructing an actual list of all the numbers available in the bag. We can add the items in descending order of their values to avoid a separate sorting step.

- We add `numOnes` instances of `1`, then `numZeros` instances of `0`, and finally `numNegOnes` instances of `-1` to a list.
- This list is now effectively sorted by value in descending order.
- Finally, we iterate through the first `k` elements of this list and calculate their sum. This sum will be the maximum possible sum.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        List<Integer> items = new ArrayList<>();
        for (int i = 0; i < numOnes; i++) {
            items.add(1);
        }
        for (int i = 0; i < numZeros; i++) {
            items.add(0);
        }
        for (int i = 0; i < numNegOnes; i++) {
            items.add(-1);
        }

        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += items.get(i);
        }
        return sum;
    }
}
```
### Algorithm
- 1. Create a new list called `items`.
- 2. Add the number `1` to the `items` list `numOnes` times.
- 3. Add the number `0` to the `items` list `numZeros` times.
- 4. Add the number `-1` to the `items` list `numNegOnes` times.
- 5. Initialize a variable `sum` to 0.
- 6. Iterate from `i = 0` to `k-1`.
- 7. In each iteration, add the value of `items.get(i)` to `sum`.
- 8. Return `sum`.

## Greedy Iterative Simulation
This approach simulates the process of picking `k` items greedily without actually creating a list of all items. It iterates `k` times, and in each step, it picks the best available item.
**Time:** O(k), as the loop runs exactly `k` times, and each operation inside the loop is constant time. · **Space:** O(1), as we only use a few variables to store the counts and the sum, regardless of the input size.
**Pros:** More efficient than the simulation with list creation approach.; Constant space complexity.
**Cons:** Still uses a loop, which is unnecessary for this problem.; Can be slightly slower than a direct mathematical calculation if `k` is large.
### Explanation
To maximize the sum, we should always pick items with the highest value first. The greedy strategy is to pick `1`s, then `0`s, then `-1`s.

We can simulate this process with a loop that runs `k` times.

- We maintain a running `sum` and keep track of the remaining counts of `numOnes`, `numZeros`, and `numNegOnes`.
- In each of the `k` iterations, we decide which item to pick:
    - If there are any `1`s left (`numOnes > 0`), we pick a `1`. We add 1 to the `sum` and decrement `numOnes`.
    - Otherwise, if there are any `0`s left (`numZeros > 0`), we pick a `0`. The sum remains unchanged, and we decrement `numZeros`.
    - Otherwise, we must pick a `-1`. We subtract 1 from the `sum` and decrement `numNegOnes`.
- After `k` iterations, the `sum` will hold the maximum possible value.

```java
class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) {
            if (numOnes > 0) {
                sum += 1;
                numOnes--;
            } else if (numZeros > 0) {
                // sum += 0;
                numZeros--;
            } else {
                sum -= 1;
                numNegOnes--;
            }
        }
        return sum;
    }
}
```
### Algorithm
- 1. Initialize `sum = 0`.
- 2. Loop `k` times, from `i = 0` to `k-1`.
- 3. Inside the loop, check if `numOnes > 0`.
- 4. If true, add 1 to `sum` and decrement `numOnes`.
- 5. Else, check if `numZeros > 0`.
- 6. If true, just decrement `numZeros` (as adding 0 doesn't change the sum).
- 7. Else (meaning we must pick a -1), subtract 1 from `sum` and decrement `numNegOnes`.
- 8. After the loop finishes, return `sum`.

## Greedy Mathematical Calculation
This is the most optimal approach. It uses a greedy strategy to directly calculate the maximum sum using conditional logic and arithmetic operations, completely avoiding any loops or extra data structures.
**Time:** O(1), as the solution involves a few conditional checks and arithmetic operations, which take constant time. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** The most efficient solution possible.; Extremely fast and requires minimal memory.
**Cons:** The logic might be slightly less intuitive at first glance compared to a direct simulation.
### Explanation
The core idea is to determine how many items of each type (`1`, `0`, `-1`) will be picked based on the greedy strategy, and then calculate the sum directly.

- **Step 1: Pick Ones.** We prioritize picking items with value `1`. We can pick at most `numOnes` of them. So, we pick `min(k, numOnes)` items. These contribute `min(k, numOnes)` to the sum. We then update `k` to reflect the remaining items to be picked.
- **Step 2: Pick Zeros.** If we still need to pick more items (`k > 0`), we move to items with value `0`. Picking `0`s does not change the sum. We pick `min(k, numZeros)` zeros and update `k`.
- **Step 3: Pick Negative Ones.** If `k` is still greater than 0, we have no choice but to pick items with value `-1`. We must pick `k` negative ones. These will decrease the sum by `k`.

This logic can be simplified into a set of if-else conditions.

```java
class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (k <= numOnes) {
            // We can pick k items, and all of them will be 1s.
            return k;
        } else if (k <= numOnes + numZeros) {
            // We pick all numOnes 1s, and the rest are 0s.
            // The sum is just the number of 1s.
            return numOnes;
        } else {
            // We pick all numOnes 1s, all numZeros 0s.
            // The remaining items must be -1s.
            // Number of -1s to pick = k - numOnes - numZeros
            // Sum = numOnes * 1 + numZeros * 0 + (k - numOnes - numZeros) * -1
            return numOnes - (k - numOnes - numZeros);
        }
    }
}
```
An even more compact way to write this:
```java
class Solution {
    public int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        int sum = 0;
        
        // Take as many ones as possible
        int onesToTake = Math.min(k, numOnes);
        sum += onesToTake;
        k -= onesToTake;
        
        if (k == 0) return sum;
        
        // Take as many zeros as possible
        int zerosToTake = Math.min(k, numZeros);
        k -= zerosToTake;
        
        if (k == 0) return sum;
        
        // Take remaining from negative ones
        int negOnesToTake = Math.min(k, numNegOnes);
        sum -= negOnesToTake;
        
        return sum;
    }
}
```
### Algorithm
- 1. Check if `k` is less than or equal to `numOnes`.
- 2. If true, it means we only pick items with value `1`. The maximum sum is `k`. Return `k`.
- 3. Else, check if `k` is less than or equal to `numOnes + numZeros`.
- 4. If true, it means we pick all `numOnes` items and the rest are `0`s. The maximum sum is `numOnes`. Return `numOnes`.
- 5. Else, it means we pick all `numOnes` items, all `numZeros` items, and the rest must be `-1`s.
- 6. The number of `-1`s to pick is `k - numOnes - numZeros`.
- 7. The total sum is `numOnes - (k - numOnes - numZeros)`. Return this value.

# Solutions
### CSharp

```csharp
public class Solution {
    public int KItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
        if (numOnes >= k) {
            return k;
        }
        if (numZeros >= k - numOnes) {
            return numOnes;
        }
        return numOnes - (k - numOnes - numZeros);
    }
}
```

### Java

```java
class Solution {
public
  int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
    if (numOnes >= k) {
      return k;
    }
    if (numZeros >= k - numOnes) {
      return numOnes;
    }
    return numOnes - (k - numOnes - numZeros);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int kItemsWithMaximumSum(int numOnes, int numZeros, int numNegOnes, int k) {
    if (numOnes >= k) {
      return k;
    }
    if (numZeros >= k - numOnes) {
      return numOnes;
    }
    return numOnes - (k - numOnes - numZeros);
  }
};

```

### Python

```python
class Solution:
    def kItemsWithMaximumSum(self, numOnes: int, numZeros: int, numNegOnes: int, k: int) -> int: if numOnes >= k: return k if numZeros >= k - numOnes: return numOnes return numOnes - (k - numOnes - numZeros)

```