Get started

Maximum Sum With Exactly K Elements — Easy Problem & Solution

You start with a score of 0 and repeat this operation exactly k times: pick the largest element of nums — call it m; add m to your score; append m + 1 to…

  • Difficulty: Easy
  • Topics: Arrays, Greedy
  • Asked at: TCS, Capgemini
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You start with a score of 0 and repeat this operation exactly k times:

  1. pick the largest element of nums — call it m;
  2. add m to your score;
  3. append m + 1 to nums.

Return the final score.

Example 1

Input: nums = [1,2,3,4,5], k = 3
Output: 18
Explanation: Take 5, then the appended 6, then the appended 7: 5 + 6 + 7 = 18.

Example 2

Input: nums = [5,5,5], k = 2
Output: 11
Explanation: 5 + 6 = 11 — duplicates of the maximum change nothing.

Example 3

Input: nums = [7], k = 1
Output: 7

Constraints

  • 1 <= nums.length <= 100000
  • 0 <= nums[i] <= 100
  • 1 <= k <= 100

How to solve Maximum Sum With Exactly K Elements

The appended value m + 1 is strictly larger than every element, so it is the next pick. The maxima form the run m, m+1, …, m+k-1, and their sum is an arithmetic series.

Approach

  1. Find m, the maximum of nums, in one pass.
  2. The score is m + (m+1) + … + (m+k-1).
  3. Close the series: k*m + k*(k-1)/2.

Why it works

By induction, if the maximum before a round is v then the round appends v + 1, which becomes the unique new maximum; so round t (0-indexed) contributes m + t. Summing t from 0 to k-1 gives the closed form.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Actually appending to the array and re-scanning is O(n·k) for no reason.
  • k*(k-1)/2 is exact in integers because k*(k-1) is always even — no floating point needed.

Reference solution

Python

from typing import List

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

JavaScript

var maximizeSum = function(nums, k) {
    var m = nums[0];
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] > m) m = nums[i];
    }
    return k * m + (k * (k - 1)) / 2;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue