3974. Maximum Total Sum of K Selected Elements - Solution

Q: Is Maximum Total Sum of K Selected Elements easy or hard?

The problem is generally classified as Medium because the optimal solution requires recognizing that selecting the k largest values maximizes the sum and implementing it efficiently using sorting, heaps, or Quickselect.

Q: Maximum Total Sum of K Selected Elements Python/Java solution

Python implementations typically use heapq (with negated values) or built-in sorting to grab the k largest elements. Java solutions often use PriorityQueue configured as a max heap or Arrays.sort followed by summing the top k values.

Q: How to solve Maximum Total Sum of K Selected Elements in O(n)?

Use the Quickselect algorithm to partition the array around the k-th largest element. After partitioning, the first k positions contain the k largest values (order does not matter). Summing those elements gives the maximum total in average O(n) time and O(1) extra space.

Q: What is the best approach for Maximum Total Sum of K Selected Elements?

Quickselect or a max-heap based greedy approach is typically the best. Quickselect finds the k largest elements in average O(n) time without sorting the entire array. If implementation simplicity matters, sorting and summing the top k elements in O(n log n) is also widely accepted in interviews.

Q: Is Maximum Total Sum of K Selected Elements asked at Google/Amazon/Meta?

Variants of this problem appear frequently in interviews at companies like Amazon, Google, and Meta. The core idea—selecting the k largest elements efficiently—tests knowledge of heaps, partial sorting, and selection algorithms such as Quickselect.

Q: What data structure is used in Maximum Total Sum of K Selected Elements?

Common implementations rely on arrays combined with either sorting or a priority queue (max heap). A heap allows repeated extraction of the maximum element in O(log n) time, while Quickselect works directly on the array using partition-based selection.

Q: What is the time complexity of Maximum Total Sum of K Selected Elements?

The complexity depends on the approach used. Sorting the array and summing the largest k elements takes O(n log n) time. Using Quickselect reduces the average complexity to O(n) with O(1) extra space, while a heap-based approach runs in about O(n + k log n).

The problem

You are given an integer array nums and two integers k and mul.

Select exactly k elements from nums. Process these elements one by one in any order you choose.

For each selected element, independently choose one of the following:

Add the element's value to the total sum, or
Multiply the element by the current value of mul and add the result to the total sum.

After processing each selected element, mul decreases by 1, regardless of which option was chosen. The current value of mul may become 0 or negative.

Return an integer denoting the maximum possible total sum.

Example 1:

Input: nums = [6,1,2,9], k = 3, mul = 2

Output: 26

Explanation:

One optimal way:

One optimal selection is nums[3] = 9, nums[0] = 6, and nums[2] = 2.
Process nums[3] = 9 first: choose multiplication, so it contributes 9 * 2 = 18. Now, mul becomes 1.
Process nums[0] = 6 next: choose multiplication, so it contributes 6 * 1 = 6. Now, mul becomes 0.
Process nums[2] = 2 last: choose addition, so it contributes 2.
The total sum is 18 + 6 + 2 = 26.

Example 2:

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

Output: 43

Explanation:

One optimal way:

One optimal selection is nums[1] = 7 and nums[2] = 5.
Process nums[1] = 7 first: choose multiplication, so it contributes 7 * 4 = 28. Now, mul becomes 3.
Process nums[2] = 5 next: choose multiplication, so it contributes 5 * 3 = 15.
The total sum is 28 + 15 = 43.

Example 3:

Input: nums = [4,4], k = 1, mul = 1

Output: 4

Explanation:

One optimal way:

One optimal selection is nums[0] = 4.
Process nums[0] = 4: choose multiplication, so it contributes 4 * 1 = 4.
The total sum is 4.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵
1 <= k <= nums.length
1 <= mul <= 10⁵

Approach overview

Problem Overview: You are given an array of integers and a value k. The task is to choose exactly k elements such that their total sum is maximized. The challenge is identifying the most efficient way to extract the largest contributions without unnecessary comparisons.

Approach 1: Brute Force Combinations (Exponential Time)

Generate every possible subset of size k and compute its sum. Track the maximum sum encountered. This can be implemented using recursion or backtracking that explores all combinations of indices. While it guarantees the correct answer, the runtime grows combinatorially: O(C(n, k) * k) time and O(k) recursion space. This approach mainly helps demonstrate baseline reasoning but is impractical for large arrays.

Approach 2: Sorting and Taking Top K (O(n log n))

Sort the array in descending order and sum the first k elements. Sorting ensures the largest values appear first, so the optimal subset is immediately visible. The algorithm performs a full sort costing O(n log n) time and uses O(1) extra space if the sort is in-place. This approach is simple, reliable, and commonly used when n is moderate.

Approach 3: Max Heap / Priority Queue (O(n log n) build, O(k log n) extraction)

Insert all elements into a max heap (priority queue). Then extract the maximum element k times and accumulate the sum. Heap operations guarantee that each extraction retrieves the current largest value. Building the heap costs O(n) or O(n log n) depending on implementation, and each extraction costs O(log n). Total complexity becomes roughly O(n + k log n) time with O(n) space. This approach is useful when the array is streamed or you want incremental maximum access using heap structures.

Approach 4: Quickselect + Partial Sum (Average O(n))

Use the Quickselect algorithm to partition the array so the k largest elements appear in the first k positions (not necessarily sorted). After partitioning, iterate through those k elements and compute their sum. Quickselect works similarly to QuickSort partitioning but only recurses into the side containing the k-th boundary. The average runtime is O(n) with O(1) extra space. This approach relies on efficient partition logic often discussed in array manipulation and divide and conquer strategies.

Recommended for interviews: Start by explaining the brute force combination approach to show you understand the search space. Then move to the sorting solution since it is straightforward and widely accepted in interviews. For strong optimization discussion, mention Quickselect because it reduces the complexity to average O(n) while avoiding a full sort.

Solution

We can sort the array nums and then select the k largest elements from the sorted array. For the i-th element, we can choose to multiply it by max(1, mul) and add it to the total sum, and then mul decreases by 1. Finally, we return the total sum.

The time complexity is O(n log n), and the space complexity is O(log n). Where n is the length of the array nums.

Python

class Solution:
    def maxSum(self, nums: list[int], k: int, mul: int) -> int:
        nums.sort()
        n = len(nums)
        ans = 0
        for i in range(n - 1, n - 1 - k, -1):
            ans += nums[i] * max(1, mul)
            mul -= 1
        return ans

Java

class Solution {
    public long maxSum(int[] nums, int k, int mul) {
        Arrays.sort(nums);
        int n = nums.length;
        long ans = 0;

        for (int i = n - 1; i >= n - k; i--) {
            int m = Math.max(1, mul);
            ans += (long) nums[i] * m;
            mul--;
        }

        return ans;
    }
}

C++

class Solution {
public:
    long long maxSum(vector<int>& nums, int k, int mul) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        long long ans = 0;

        for (int i = n - 1; i >= n - k; --i) {
            int m = max(1, mul);
            ans += 1LL * nums[i] * m;
            mul--;
        }

        return ans;
    }
};

TypeScript

function maxSum(nums: number[], k: number, mul: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;

    for (let i = n - 1; i >= n - k; i--) {
        const m = Math.max(1, mul);
        ans += nums[i] * m;
        mul--;
    }

    return ans;
}

func maxSum(nums []int, k int, mul int) int64 {
    sort.Ints(nums)
    n := len(nums)
    var ans int64 = 0

    for i := n - 1; i >= n-k; i-- {
        m := max(1, mul)
        ans += int64(nums[i]) * int64(m)
        mul--
    }

    return ans
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Combinations	O(C(n,k) * k)	O(k)	Conceptual baseline or very small arrays
Sorting + Top K	O(n log n)	O(1)	Simple and reliable solution for most constraints
Max Heap (Priority Queue)	O(n + k log n)	O(n)	When you need repeated maximum extraction or streaming data
Quickselect + Partial Sum	O(n) average	O(1)	Best theoretical performance without fully sorting the array

Frequently asked questions

Is Maximum Total Sum of K Selected Elements easy or hard?

The problem is generally classified as Medium because the optimal solution requires recognizing that selecting the k largest values maximizes the sum and implementing it efficiently using sorting, heaps, or Quickselect.

Maximum Total Sum of K Selected Elements Python/Java solution

Python implementations typically use heapq (with negated values) or built-in sorting to grab the k largest elements. Java solutions often use PriorityQueue configured as a max heap or Arrays.sort followed by summing the top k values.

How to solve Maximum Total Sum of K Selected Elements in O(n)?

Use the Quickselect algorithm to partition the array around the k-th largest element. After partitioning, the first k positions contain the k largest values (order does not matter). Summing those elements gives the maximum total in average O(n) time and O(1) extra space.

What is the best approach for Maximum Total Sum of K Selected Elements?

Quickselect or a max-heap based greedy approach is typically the best. Quickselect finds the k largest elements in average O(n) time without sorting the entire array. If implementation simplicity matters, sorting and summing the top k elements in O(n log n) is also widely accepted in interviews.

Is Maximum Total Sum of K Selected Elements asked at Google/Amazon/Meta?

Variants of this problem appear frequently in interviews at companies like Amazon, Google, and Meta. The core idea—selecting the k largest elements efficiently—tests knowledge of heaps, partial sorting, and selection algorithms such as Quickselect.

What data structure is used in Maximum Total Sum of K Selected Elements?

Common implementations rely on arrays combined with either sorting or a priority queue (max heap). A heap allows repeated extraction of the maximum element in O(log n) time, while Quickselect works directly on the array using partition-based selection.

What is the time complexity of Maximum Total Sum of K Selected Elements?

The complexity depends on the approach used. Sorting the array and summing the largest k elements takes O(n log n) time. Using Quickselect reduces the average complexity to O(n) with O(1) extra space, while a heap-based approach runs in about O(n + k log n).

Maximum Total Sum of K Selected Elements solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Maximum Total Sum of K Selected Elements solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems