Maximum Total Sum of K Selected Elements - Solution & Explanation

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.