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.

Examples

Example 1

1
2
3
4
5
6
7
8

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

1
2
3
4
5
6
7

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

Solution

Method 1 – Greedy with Max-Heap

Intuition

To maximize the score, always pick the largest element from the array, increment it, and repeat for k times. This is a classic greedy approach using a max-heap to efficiently get the largest element each time.

Approach

  1. Build a max-heap from the input array.
  2. For k times:
    • Pop the largest element from the heap.
    • Add its value to the score.
    • Push back the incremented value (m + 1) into the heap.
  3. Return the final score after k operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int maximizeSum(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        int ans = 0;
        while (k--) {
            int m = pq.top(); pq.pop();
            ans += m;
            pq.push(m + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import "container/heap"
type MaxHeap []int
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
func maximizeSum(nums []int, k int) int {
    h := MaxHeap(nums)
    heap.Init(&h)
    ans := 0
    for i := 0; i < k; i++ {
        m := heap.Pop(&h).(int)
        ans += m
        heap.Push(&h, m+1)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.*;
class Solution {
    public int maximizeSum(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int x : nums) pq.offer(x);
        int ans = 0;
        for (int i = 0; i < k; ++i) {
            int m = pq.poll();
            ans += m;
            pq.offer(m + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

import java.util.PriorityQueue
class Solution {
    fun maximizeSum(nums: IntArray, k: Int): Int {
        val pq = PriorityQueue<Int>(compareByDescending { it })
        nums.forEach { pq.add(it) }
        var ans = 0
        repeat(k) {
            val m = pq.poll()
            ans += m
            pq.add(m + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

import heapq
class Solution:
    def maximizeSum(self, nums: list[int], k: int) -> int:
        pq = [-x for x in nums]
        heapq.heapify(pq)
        ans = 0
        for _ in range(k):
            m = -heapq.heappop(pq)
            ans += m
            heapq.heappush(pq, -(m + 1))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

use std::collections::BinaryHeap;
impl Solution {
    pub fn maximize_sum(nums: Vec<i32>, k: i32) -> i32 {
        let mut heap = BinaryHeap::from(nums);
        let mut ans = 0;
        for _ in 0..k {
            let m = heap.pop().unwrap();
            ans += m;
            heap.push(m + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    maximizeSum(nums: number[], k: number): number {
        nums.sort((a, b) => b - a);
        let ans = 0, m = nums[0];
        for (let i = 0; i < k; ++i) {
            ans += m;
            m++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n + k log n), where n is the length of nums. Building the heap is O(n), each operation is O(log n).
  • 🧺 Space complexity: O(n), for the heap.