Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

LeetCode 2656 - Maximum Sum With Exactly K Elements

Problem Understanding

The problem gives us an integer array nums and an integer k. We must perform exactly k operations. During each operation, we choose one element from the array, add its value to our score, remove it from the array, and then insert a new element equal to the chosen value plus one.

The goal is to maximize the total score after exactly k operations.

The important detail is that after choosing a number m, the array gains a new number m + 1. This means that if we repeatedly choose the current maximum value, the maximum value keeps increasing by one after every operation.

For example, if the largest number is 5:

First pick gives 5
The array now contains 6
Second pick gives 6
The array now contains 7
Third pick gives 7

This forms a consecutive increasing sequence.

The input consists of:

nums, an array of positive integers
k, the exact number of operations we must perform

The output is a single integer representing the maximum score possible.

The constraints are very small:

nums.length <= 100
nums[i] <= 100
k <= 100

These constraints mean that even a straightforward simulation would work comfortably within time limits. However, the problem is designed to test whether we recognize the greedy pattern and arithmetic progression.

There are several important edge cases to consider:

Arrays where all elements are equal
Arrays containing only one element
k = 1, where we simply return the maximum element
Repeated selections of the same increasing maximum value
Small arrays with large k

The problem guarantees that all numbers are positive integers, so we never need to handle empty arrays or negative values.

Approaches

Brute Force Approach

The brute force solution directly simulates the process exactly as described.

For each of the k operations:

Find the current maximum value in the array.
Add it to the score.
Remove that value.
Insert the value plus one back into the array.

This works because it follows the problem statement literally. Since choosing the largest available value always gives the greatest immediate contribution, the brute force simulation will produce the optimal result.

However, repeatedly searching for the maximum element can be inefficient. Each operation requires scanning the array to locate the maximum value, giving a time complexity of O(n * k).

Even though the constraints are small enough for this to pass, we can do better by recognizing a mathematical pattern.

Optimal Greedy Approach

The key observation is that we should always pick the current maximum number.

Suppose the maximum value in nums is max_num.

After choosing it once:

We gain max_num
The array gains max_num + 1

Now the new maximum becomes max_num + 1.

After the second operation:

We gain max_num + 1
The array gains max_num + 2

This continues for exactly k operations.

Therefore, the sequence of chosen numbers is:

max_num, max_num + 1, max_num + 2, ..., max_num + (k - 1)

This is an arithmetic progression.

The sum of this sequence can be computed directly:

k * max_num + (0 + 1 + 2 + ... + (k - 1))

Using the arithmetic series formula:

0 + 1 + 2 + ... + (k - 1) = (k - 1) * k / 2

So the final answer becomes:

k * max_num + (k * (k - 1)) / 2

This avoids simulation entirely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(1)	Simulates each operation directly
Optimal	O(n)	O(1)	Uses arithmetic progression formula

Algorithm Walkthrough

Optimal Algorithm

Find the maximum element in the array.

We first determine the largest value in nums because choosing the largest available number always maximizes the score at every step. 2. Recognize the increasing sequence.

After selecting the maximum value once, that value becomes one larger and re-enters the array. This means the next optimal choice is larger by one.

The selected values form this sequence:

max_num
max_num + 1
max_num + 2
...
max_num + (k - 1)

Compute the sum of the arithmetic sequence.

Instead of simulating the process, we directly compute:

k * max_num + (0 + 1 + ... + (k - 1))

Use the arithmetic series formula.

The sum of integers from 0 to k - 1 is:

$0+1+2+\cdots+(k-1)=\frac{k(k-1)}{2}$ 5. Return the final result.

The maximum score is:

$\text{answer}=k\cdot \max(nums)+\frac{k(k-1)}{2}$

Why it works

The greedy strategy works because after selecting the current maximum value m, the replacement value becomes m + 1, which is still at least as large as every other number in the array. Therefore, repeatedly choosing the evolving maximum always produces the largest possible score at every step. Since the chosen values form a consecutive increasing sequence, the arithmetic progression formula gives the exact optimal total.

Python Solution

from typing import List

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

The implementation begins by finding the largest element in the array using Python's built-in max() function.

Once we know the maximum value, we use the arithmetic progression formula directly. The first part, k * max_num, accounts for adding the starting maximum value k times. The second part, (k * (k - 1)) // 2, adds the incremental increases that occur after each operation.

Integer division // is used because the formula always produces an integer result.

The implementation is concise because the mathematical observation removes the need for simulation or additional data structures.

Go Solution

func maximizeSum(nums []int, k int) int {
    maxNum := nums[0]

    for _, num := range nums {
        if num > maxNum {
            maxNum = num
        }
    }

    return k*maxNum + (k*(k-1))/2
}

The Go solution follows the same logic as the Python version.

Since Go does not provide a built-in max() function for slices, we manually iterate through the array to find the largest value.

All computations use the built-in int type. Given the problem constraints, integer overflow is not a concern because the largest possible answer is small.

No extra slices or data structures are required, so the solution maintains constant space complexity.

Worked Examples

Example 1

Input: nums = [1,2,3,4,5], k = 3

The maximum value is:

max_num = 5

The chosen sequence becomes:

5, 6, 7

Step-by-Step Table

Operation	Chosen Value	Score After Operation	New Inserted Value
1	5	5	6
2	6	11	7
3	7	18	8

Final answer:

Using the formula:

3 * 5 + (3 * 2) / 2
= 15 + 3
= 18

Example 2

Input: nums = [5,5,5], k = 2

The maximum value is:

max_num = 5

The chosen sequence becomes:

5, 6

Step-by-Step Table

Operation	Chosen Value	Score After Operation	New Inserted Value
1	5	5	6
2	6	11	7

Final answer:

Using the formula:

2 * 5 + (2 * 1) / 2
= 10 + 1
= 11

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the array once to find the maximum element
Space	O(1)	Only a few variables are used

The algorithm only requires a single pass through the array to determine the maximum value. All remaining operations are constant-time arithmetic calculations. No auxiliary data structures proportional to the input size are allocated.

Test Cases

from typing import List

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

solution = Solution()

assert solution.maximizeSum([1,2,3,4,5], 3) == 18  # Provided example 1
assert solution.maximizeSum([5,5,5], 2) == 11  # Provided example 2

assert solution.maximizeSum([1], 1) == 1  # Single element, single operation
assert solution.maximizeSum([10], 3) == 33  # Single element reused repeatedly
assert solution.maximizeSum([1,1,1,1], 5) == 15  # All elements identical
assert solution.maximizeSum([2,4,6,8], 1) == 8  # k equals 1
assert solution.maximizeSum([100], 100) == 14950  # Maximum constraints
assert solution.maximizeSum([3,7,2], 4) == 34  # Repeatedly increasing maximum
assert solution.maximizeSum([9,1,5], 2) == 19  # Maximum selected twice
assert solution.maximizeSum([4,4,4,4], 3) == 15  # Duplicate maximum values

Test Case Summary

Test	Why
`[1,2,3,4,5], k=3`	Validates the main example
`[5,5,5], k=2`	Tests identical values
`[1], k=1`	Smallest valid input
`[10], k=3`	Ensures repeated reuse works
`[1,1,1,1], k=5`	Tests repeated increments from duplicates
`[2,4,6,8], k=1`	Verifies single operation behavior
`[100], k=100`	Stresses upper constraints
`[3,7,2], k=4`	Tests consecutive increasing sequence
`[9,1,5], k=2`	Confirms greedy choice correctness
`[4,4,4,4], k=3`	Ensures duplicate maximum handling

Edge Cases

Single Element Array

If the array contains only one element, that element will always be selected repeatedly because it is the only available choice. After every operation, the inserted value becomes larger by one. A buggy implementation might incorrectly assume multiple elements are required, but the formula naturally handles this scenario.

For example:

nums = [10], k = 3

The sequence becomes:

10, 11, 12

The implementation correctly computes the result directly from the arithmetic progression formula.

All Elements Equal

When every element has the same value, the first selection can be any index because they are identical. After the first operation, the newly inserted value becomes larger than all remaining elements and should continue being selected.

For example:

nums = [5,5,5], k = 2

A naive implementation might repeatedly pick arbitrary equal elements instead of tracking the evolving maximum properly. Our mathematical approach avoids this issue entirely.

Large k Value

When k is large relative to the array size, repeated selection and reinsertion become especially important. A simulation-based solution could become unnecessarily repetitive.

For example:

nums = [100], k = 100

The chosen sequence ranges from 100 through 199.

Instead of simulating 100 separate operations, the implementation computes the result instantly using the arithmetic series formula, guaranteeing both correctness and efficiency.