Skip to main content
Talentd
Talentd#1 Freshers Platform
Find Work
Learn
Tools
Post a JobFreeJoin Community
TalentdTalentd

Maximum Total Sum of K Selected Elements - Solution & Explanation

MediumArrayGreedySorting7 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= nums.length
  • 1 <= mul <= 105

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force CombinationsO(C(n,k) * k)O(k)Conceptual baseline or very small arrays
Sorting + Top KO(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 SumO(n) averageO(1)Best theoretical performance without fully sorting the array

Video Solution

Maximum Total Sum of K Selected Elements | LeetCode 3974 | Weekly Contest 508 | Developer Coder • Developer Coder • 293 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Maximum Total Sum of K Selected Elements with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays