Scale Engineer

Maximum Sum With Exactly K Elements

Easy
#2413Time: 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.
Patterns
Greedy
Data structures
Array

Prompt

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

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 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.

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.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem