# Maximum Sum With Exactly K Elements 
**Difficulty:** EASY
[External](https://leetcode.com/problems/maximum-sum-with-exactly-k-elements)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-with-exactly-k-elements
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `nums` and an integer `k`. Your task is to perform the following operation **exactly** `k` times in order to maximize your score:

1. Select an element `m` from `nums`.
2. Remove the selected element `m` from the array.
3. Add a new element with a value of `m + 1` to the array.
4. Increase your score by `m`.

Return _the maximum score you can achieve after performing the operation exactly_ `k` _times._

**Example 1:**

**Input:** nums = [1,2,3,4,5], k = 3
**Output:** 18
**Explanation:** We need to choose exactly 3 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]
For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]
For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]
So, we will return 18.
It can be proven, that 18 is the maximum answer that we can achieve.

**Example 2:**

**Input:** nums = [5,5,5], k = 2
**Output:** 11
**Explanation:** We need to choose exactly 2 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]
For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]
So, we will return 11.
It can be proven, that 11 is the maximum answer that we can achieve.

**Constraints:**

* `1 <= nums.length <= 100`
* `1 <= nums[i] <= 100`
* `1 <= k <= 100`

# Approaches
## Simulation with Repeated Sorting
This approach directly simulates the process described in the problem. In each of the `k` iterations, we need to find and select the maximum element from the array. A straightforward way to find the maximum is to sort the array and pick the last element. After selecting the maximum element `m`, we add it to our score and update its value in the array to `m + 1` for the next iteration.
**Time:** O(k * n log n), where `n` is the number of elements in `nums` and `k` is the number of operations. In each of the `k` iterations, we sort the array, which takes O(n log n) time. · **Space:** O(log n) or O(n), depending on the implementation of the sorting algorithm used. For instance, `Arrays.sort()` in Java for primitives uses a dual-pivot quicksort, which has an average space complexity of O(log n).
**Pros:** Simple to understand and implement as it directly follows the problem statement.
**Cons:** Inefficient due to repeated sorting of the entire array, especially for large `k` or `n`.
### Explanation
This method provides a brute-force simulation of the game. For each of the `k` turns, we sort the entire array to find the current maximum value. This guarantees that we always pick the largest number available, which is the greedy choice to maximize the score. Once we pick the maximum element `m`, we add it to our running total and then update that element's value to `m+1` in the array, preparing for the next turn.

```java
import java.util.Arrays;

class Solution {
    public int maximizeSum(int[] nums, int k) {
        int score = 0;
        for (int i = 0; i < k; i++) {
            Arrays.sort(nums);
            int m = nums[nums.length - 1];
            score += m;
            nums[nums.length - 1] = m + 1;
        }
        return score;
    }
}
```
### Algorithm
- Initialize a variable `score` to 0.
- Loop `k` times. In each iteration:
  - Sort the `nums` array in ascending order.
  - Identify the maximum element, which is the last element of the sorted array, let's call it `m`.
  - Add `m` to the `score`.
  - Replace the last element in the array with `m + 1`.
- After `k` iterations, return the total `score`.

## Simulation with a Max Heap
To optimize finding the maximum element in each step, we can use a data structure designed for this purpose: a max heap (implemented as a Priority Queue in Java). We first build a max heap from the initial elements of `nums`. Then, for `k` iterations, we extract the maximum element, add it to the score, and insert the incremented value back into the heap. This avoids re-sorting the entire array each time.
**Time:** O(n + k log n). Building the heap from `n` elements takes O(n) time. Each of the `k` operations involves one extraction (`poll`) and one insertion (`add`), both of which take O(log n) time. · **Space:** O(n), as the priority queue needs to store all `n` elements of the array.
**Pros:** More efficient than the repeated sorting approach.; Good for scenarios where you need to repeatedly find the max/min element.
**Cons:** Requires extra space for the heap.; Still performs more work than necessary, as the logic can be simplified further.
### Explanation
Instead of sorting the entire array in every step, a more efficient way to repeatedly find the maximum element is to use a max heap. We can initialize a priority queue with all the numbers from the input array. A priority queue keeps the elements in a semi-ordered way, such that the largest (or smallest) element can be retrieved in logarithmic time. For each of the `k` steps, we extract the max element, add it to our score, and then insert the element plus one back into the heap. This is significantly faster than the repeated sorting approach.

```java
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int maximizeSum(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : nums) {
            maxHeap.add(num);
        }

        int score = 0;
        for (int i = 0; i < k; i++) {
            int m = maxHeap.poll();
            score += m;
            maxHeap.add(m + 1);
        }
        return score;
    }
}
```
### Algorithm
- Create a max Priority Queue. In Java, this can be done by providing a reverse order comparator.
- Add all elements from the `nums` array into the priority queue.
- Initialize `score` to 0.
- Loop `k` times:
  - Extract the maximum element `m` from the priority queue (using `poll()`).
  - Add `m` to the `score`.
  - Insert `m + 1` back into the priority queue (using `add()`).
- Return the final `score`.

## Optimal Mathematical Approach
The most efficient approach comes from a key observation. To maximize the score, we should always pick the largest available number. If we start with the largest number in the initial array, say `max_val`, the numbers we will pick in the `k` operations will be `max_val`, `max_val + 1`, `max_val + 2`, ..., `max_val + k - 1`. The problem then reduces to finding the initial maximum element and calculating the sum of this arithmetic progression.
**Time:** O(n), where `n` is the number of elements in `nums`. This time is dominated by the single pass required to find the initial maximum element. The subsequent calculation is O(1) if using the formula, or O(k) if using a simple loop. · **Space:** O(1), as we only use a few variables to store the maximum value and the score, regardless of the input size.
**Pros:** Most efficient solution with linear time and constant space complexity.; Avoids any complex data structures or repeated computations.
**Cons:** Requires a logical leap to see the pattern and simplify the problem into a mathematical formula.
### Explanation
A closer look at the greedy strategy reveals a simple mathematical pattern. Since we always pick the largest element, and the new element `m+1` will always be larger than any other original element, the sequence of numbers we pick is deterministic. It starts with the initial maximum element of `nums`, let's call it `max_val`, and continues as `max_val + 1`, `max_val + 2`, and so on, for `k` terms. This is an arithmetic progression. We can find the sum by first finding the initial `max_val` in a single pass through the array, and then either summing up the `k` terms in a simple loop or by using the arithmetic series sum formula: `Sum = k * max_val + k * (k - 1) / 2`.

```java
import java.util.Arrays;

class Solution {
    public int maximizeSum(int[] nums, int k) {
        // Find the maximum element in the initial array.
        int maxVal = 0;
        for (int num : nums) {
            if (num > maxVal) {
                maxVal = num;
            }
        }
        
        // The numbers we pick form an arithmetic sequence.
        // We can sum them up in a simple loop.
        int score = 0;
        for (int i = 0; i < k; i++) {
            score += maxVal;
            maxVal++;
        }
        
        return score;
    }
}
```
Alternatively, using the direct formula:
```java
import java.util.Arrays;

class Solution {
    public int maximizeSum(int[] nums, int k) {
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }
        // Sum of arithmetic series: k*a + k*(k-1)*d/2
        // Here, a = maxVal and d = 1
        return k * maxVal + k * (k - 1) / 2;
    }
}
```
### Algorithm
- Find the maximum element, `max_val`, in the input array `nums`.
- The sequence of numbers we add to the score is an arithmetic progression: `max_val, max_val + 1, ..., max_val + k - 1`.
- We can calculate the sum of this series directly. The sum of an arithmetic series is `(number of terms / 2) * (first term + last term)`.
- An even simpler way is to calculate it iteratively or using the formula `score = k * max_val + k * (k - 1) / 2`.
- Return the calculated score.

# Solutions
### Java

```java
class Solution {
public
  int maximizeSum(int[] nums, int k) {
    int x = 0;
    for (int v : nums) {
      x = Math.max(x, v);
    }
    return k * x + k * (k - 1) / 2;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximizeSum(vector<int> &nums, int k) {
    int x = *max_element(nums.begin(), nums.end());
    return k * x + k * (k - 1) / 2;
  }
};

```

### Python

```python
class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int: x = max(nums) return k * x + k * (k - 1) // 2

```