Maximum Sum With Exactly K Elements
EasyPrompt
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:
- Select an element
mfromnums. - Remove the selected element
mfrom the array. - Add a new element with a value of
m + 1to the array. - 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 <= 1001 <= nums[i] <= 1001 <= k <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Find the maximum element,
max_val, in the input arraynums. - 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.
Walkthrough
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.
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:
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize a variable
scoreto 0. - Loop
ktimes. In each iteration:- Sort the
numsarray in ascending order. - Identify the maximum element, which is the last element of the sorted array, let's call it
m. - Add
mto thescore. - Replace the last element in the array with
m + 1.
- Sort the
- After
kiterations, return the totalscore.
Walkthrough
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.
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; }}Complexity
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).
Trade-offs
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
korn.
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.
Algorithm
- Create a max Priority Queue. In Java, this can be done by providing a reverse order comparator.
- Add all elements from the
numsarray into the priority queue. - Initialize
scoreto 0. - Loop
ktimes:- Extract the maximum element
mfrom the priority queue (usingpoll()). - Add
mto thescore. - Insert
m + 1back into the priority queue (usingadd()).
- Extract the maximum element
- Return the final
score.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};class Solution: def maximizeSum(self, nums: List[int], k: int) -> int: x = max(nums) return k * x + k * (k - 1) // 2Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.