Skip to content

2656. Maximum Sum With Exactly K Elements

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:

  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

 

Solutions

Solution 1: Greedy + Mathematics

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 \(k\)th 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)\).

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

1
2
3
4
5
6
7
8
9
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;
    }
}

1
2
3
4
5
6
7
class Solution {
public:
    int maximizeSum(vector<int>& nums, int k) {
        int x = *max_element(nums.begin(), nums.end());
        return k * x + k * (k - 1) / 2;
    }
};

1
2
3
4
func maximizeSum(nums []int, k int) int {
    x := slices.Max(nums)
    return k*x + k*(k-1)/2
}

1
2
3
4
function maximizeSum(nums: number[], k: number): number {
    const x = Math.max(...nums);
    return k * x + (k * (k - 1)) / 2;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn maximize_sum(nums: Vec<i32>, k: i32) -> i32 {
        let mut mx = 0;

        for &n in &nums {
            if n > mx {
                mx = n;
            }
        }

        ((0 + k - 1) * k) / 2 + k * mx
    }
}

Solution 2

1
2
3
4
5
6
7
impl Solution {
    pub fn maximize_sum(nums: Vec<i32>, k: i32) -> i32 {
        let mx = *nums.iter().max().unwrap_or(&0);

        ((0 + k - 1) * k) / 2 + k * mx
    }
}

Comments