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:
m from nums.m from the array.m + 1 to the array.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
Problem Overview: You receive an integer array nums and an integer k. In each of the k operations, pick the maximum element, add it to the score, then increase that element by 1 and place it back. The goal is to maximize the total score after exactly k picks.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
The optimal move each step is always the current maximum number. Sort the array and take the largest value m. Because the chosen value increases by 1 after every pick, the next best value becomes m + 1, then m + 2, and so on. Instead of re-sorting or scanning each time, treat the sequence as an arithmetic progression: m + (m+1) + ... + (m+k-1). This greedy observation eliminates repeated searches. Sorting is used only to find the initial maximum element. This approach works well when the array is static and you only need the largest starting value. It relies on the greedy property that selecting the current maximum always leads to the optimal sum. Related ideas often appear in Greedy and Array problems.
Approach 2: Priority Queue / Max Heap (O(k log n) time, O(n) space)
A more direct simulation uses a max heap. Insert all numbers from nums into a priority queue. For each of the k operations, extract the largest value, add it to the score, increment it by 1, and push it back into the heap. The heap guarantees O(log n) insertion and removal while always exposing the maximum element. This approach closely follows the problem statement and is easier to reason about during interviews when the arithmetic pattern is not immediately obvious. Priority queues are a standard tool for repeatedly accessing the largest or smallest element, commonly seen in Heap and greedy-style optimization problems.
Recommended for interviews: Interviewers typically expect the greedy insight. Recognizing that the maximum element grows linearly after each selection lets you compute the sum directly instead of simulating every step. Showing the heap simulation first demonstrates understanding of the problem mechanics, while the greedy arithmetic approach shows optimization skills and stronger algorithmic thinking.
The problem can be approached using a greedy strategy. The idea is to always maximize the immediate gain by selecting the largest number available, increasing it by 1 to continue keeping it as a valuable pick for future iterations. By maintaining a sorted list and always taking from the largest element, we can ensure that every selection maximizes the score increment.
This Python function implements the greedy approach. It sorts the array in descending order and iteratively chooses the maximum number, updates the score, increases the number, and sorts again to maintain order.
Time Complexity: O(k * n log n) due to the repeated sorting operations.
Space Complexity: O(1) since sorting is done in-place.
To avoid continuous sorting, use a priority queue (max-heap) to always fetch the largest element efficiently. By using a max-heap, the selection of the maximum element and the subsequent insertion of the incremented element can be performed in logarithmic time, optimizing the execution for scenarios with larger inputs or iterations.
This C++ solution uses a max-heap to efficiently keep track of the largest number, incrementing it and inserting it back to maintain the largest selection available for the next iterations.
C++
JavaScript
Time Complexity: O(k log n) because each heap operation takes logarithmic time.
Space Complexity: O(n) for storing elements in the heap.
We notice that to make the final score maximum, we should make each choice as large as possible. Therefore, we select the largest element x in the array for the first time, x+1 for the second time, x+2 for the third time, and so on, until the kth time we select x+k-1. This way of selection ensures that the element selected each time is the largest in the current array, so the final score is also the largest. The answer is k x sum plus 0+1+2+cdots+(k-1), that is, k times x + (k - 1) times k / 2.
Time complexity is O(n), where n is the length of the array. Space complexity is O(1).
Rust
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(k * n log n) due to the repeated sorting operations. |
| Priority Queue Approach | Time Complexity: O(k log n) because each heap operation takes logarithmic time. |
| Greedy + Mathematics | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) | When you only need the maximum element and want a direct greedy or mathematical solution |
| Priority Queue (Max Heap) | O(k log n) | O(n) | When simulating each operation or when repeatedly retrieving and updating the maximum element |
Leetcode 2656 Maximum Sum With Exactly K Elements • AlgorithmicIQ • 879 views views
Watch 8 more video solutions →Practice Maximum Sum With Exactly K Elements with our built-in code editor and test cases.
Practice on FleetCode