Maximum Sum With Exactly K Elements

EASY

Description

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 m from nums.
Remove the selected element m from the array.
Add a new element with a value of m + 1 to 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 <= 100
1 <= nums[i] <= 100
1 <= k <= 100

Approaches

Checkout 3 different approaches to solve Maximum Sum With Exactly K Elements . Click on different approaches to view the approach and algorithm in detail.

Optimal Mathematical Approach

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a few variables to store the maximum value and the score, regardless of the input size.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Sum With Exactly K Elements . Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Sum With Exactly K Elements

Patterns:

Greedy

Data Structures:

Array