Maximum Sum With Exactly K Elements - Practice Coding Problems

Maximum Sum With Exactly K Elements - Problem

Array Greedy Easy

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.

Input & Output

Example 1 — Basic Case

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

› Output: 18

💡 Note: Operation 1: Select 5 (max), score = 5, array becomes [6,2,1]. Operation 2: Select 6 (max), score = 11, array becomes [7,2,1]. Operation 3: Select 7 (max), score = 18. Total score = 5 + 6 + 7 = 18.

Example 2 — Single Element

$ Input: nums = [10], k = 2

› Output: 21

💡 Note: Operation 1: Select 10, score = 10, array becomes [11]. Operation 2: Select 11, score = 21. Total score = 10 + 11 = 21.

Example 3 — Larger Array

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

› Output: 26

💡 Note: Always select maximum: 5 + 6 + 7 + 8 = 26. The other elements don't matter since we keep incrementing the maximum.

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100
1 ≤ k ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input

Array [5,2,1] with k=3 operations

Process

Always select maximum, then increment it

Output

Sum of selected elements: 18

Key Takeaway

🎯 Key Insight: Always selecting the maximum element and incrementing it creates an arithmetic sequence that maximizes the total score

Asked in

G Google 25 a Amazon 18

The key insight is to always select the maximum element to maximize the score. Since we increment the selected element each time, we get an arithmetic sequence starting from the maximum value. The optimal approach uses the formula k×M + k×(k-1)/2 where M is the maximum element. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Optimization	O(n)	O(1)	Always select the current maximum element, then increment it for future operations
Simulate Each Operation	O(k × n)	O(1)	Perform k operations, each time finding and selecting the maximum element

Greedy Optimization — Algorithm Steps

Find the maximum element in the original array
Calculate arithmetic sequence: M + (M+1) + (M+2) + ... + (M+k-1)
Use formula: k*M + k*(k-1)/2

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Maximum

Identify the largest element in array

Arithmetic Sequence

Operations create sequence: M, M+1, M+2, ..., M+k-1

Apply Formula

Sum = k*M + k*(k-1)/2

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int k) {
    // Find the maximum element
    int maxVal = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] > maxVal) {
            maxVal = nums[i];
        }
    }
    
    // Calculate arithmetic sequence sum: maxVal + (maxVal+1) + ... + (maxVal+k-1)
    // Formula: k * maxVal + k*(k-1)/2
    int score = k * maxVal + k * (k - 1) / 2;
    return score;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[100];
    int numsSize = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through array to find maximum element

✓ Linear Growth

Space Complexity

O(1)

Only using variables for calculation, no extra data structures

✓ Linear Space

23.1K Views

Medium Frequency

~10 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler