Maximum Sum With Exactly K Elements

Difficulty: Easy | Acceptance: 80.60% | Paid: No Topics: Array, Greedy

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 index i and add nums[i] to your score.
2. Increment nums[i] by 1.

Return the maximum score you can achieve.

• Examples
• Constraints
• Sorting and Greedy
• Max Heap (Priority Queue)
• Mathematical Formula

Examples

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

Sorting and Greedy

Intuition To maximize the sum, we should always pick the largest available element. After picking, we increment it by 1, which keeps it as a strong candidate for the next pick.

Steps

• Sort the array in ascending order
• For each of k operations, pick the last (largest) element
• Add it to the score and increment it by 1
• The array remains sorted since we only increase the largest element

class Solution:
    def maximizeSum(self, nums: list[int], k: int) -> int:
        nums.sort()
        score = 0
        for _ in range(k):
            score += nums[-1]
            nums[-1] += 1
        return score

Complexity

• Time: O(n log n + k) for sorting and k operations
• Space: O(1) or O(n) depending on sorting implementation
• Notes: Simple and intuitive, but sorting is unnecessary overhead

Max Heap (Priority Queue)

Intuition Use a max heap to efficiently retrieve and update the maximum element in each operation without sorting the entire array.

Steps

• Build a max heap from all elements
• For each of k operations, extract the maximum element
• Add it to the score, increment by 1, and push back to heap
• The heap maintains the maximum element at the top

import heapq

class Solution:
    def maximizeSum(self, nums: list[int], k: int) -> int:
        # Python has min-heap, so negate values for max-heap
        max_heap = [-x for x in nums]
        heapq.heapify(max_heap)
        score = 0
        for _ in range(k):
            val = -heapq.heappop(max_heap)
            score += val
            heapq.heappush(max_heap, -(val + 1))
        return score

Complexity

• Time: O(n + k log n) for heap construction and k operations
• Space: O(n) for the heap
• Notes: More efficient than sorting for large arrays with small k

Mathematical Formula

Intuition Since we always pick the maximum element and increment it, the sequence of picked values forms an arithmetic progression starting from the maximum element.

Steps

• Find the maximum element in the array
• The k picked values will be: max, max+1, max+2, …, max+k-1
• Use arithmetic series formula: k × max + k × (k-1) / 2

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

Complexity

• Time: O(n) to find the maximum element
• Space: O(1) constant extra space
• Notes: Optimal solution with minimal time and space complexity