Maximum Sum With Exactly K Elements — Editorial

Opening the reading…

Intuitionwhy the same element remains the best choice after every operation

Suppose the current maximum value is x. Choosing any smaller value can score at most x - 1, while choosing x scores x and immediately changes that element to x + 1. The changed element is therefore still at least as large as every element that was not chosen, so choosing it again is never worse than switching to another element.

If the initial maximum is M, the scores from the k operations are M, M + 1, M + 2, and so on through M + k - 1. Their sum is kM + k(k - 1) / 2. The whole problem therefore reduces to finding the initial maximum; no simulation or sorting is needed.

Approachturning the greedy choice into one formula

Scan nums and find its largest value, because the first operation should use the element that gives the greatest possible score.

Call the largest value maxVal, because the selected element starts the sequence of scores and every later score depends on it.

Recognize that after selecting maxVal, the same element becomes maxVal + 1 and remains a maximum, so selecting it again cannot reduce the score.

Represent the k selected values as an arithmetic progression from maxVal through maxVal + k - 1, because each operation increases the chosen value by exactly one.

Sum that progression with k * maxVal + k * (k - 1) / 2, because the first term contributes k times and the increasing offsets contribute 0 through k - 1.

Return the formula directly, because it already accounts for exactly k operations and no array mutation is needed.

Complexitythe scan is the only work that depends on the array

MEASURE	BOUND	WHY
Time	O(n)	The maximum scan examines each of the n input elements once. The final formula uses a fixed number of arithmetic operations, so it adds O(1) work and nothing is revisited.
Space	O(1) extra	Only maxVal and a few arithmetic variables are needed. The input array is not copied, and there is no returned collection whose storage would need to be counted; the bound does not degrade with any input shape.

Here n is the number of elements in nums and k is the required number of operations.

Annotated solutionC++ · greedy formula · no simulation required

CPPFind the initial maximum and sum the resulting arithmetic progression.

#include <algorithm>
#include <vector>
using namespace std;

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

The important line is the return expression. The term k * maxVal counts the starting value once for each operation, while k * (k - 1) / 2 sums the increases added before each later selection. The increase offsets are 0, 1, 2, through k - 1, so using k * k / 2 would include one extra increase and produce the wrong score.