Maximum Subarray Sum After at Most K Swaps - Solution & Explanation

Problem Overview: Given an integer array and an integer k, choose a subarray and perform at most k swaps between elements inside the subarray and elements outside it. The goal is to maximize the final sum of the chosen subarray.

Approach 1: Brute Force Subarray Enumeration (O(n² log n) time, O(n) space)

Enumerate every possible subarray using two pointers. For each subarray, collect its elements and the elements outside the subarray. Sort the subarray in ascending order and the outside elements in descending order. Greedily perform up to k swaps where an outside element is larger than the smallest element currently inside the subarray. Each swap increases the sum. This approach directly models the optimal swap decision but becomes expensive because every subarray requires sorting or heap operations.

Approach 2: Greedy with Heaps for Each Subarray (O(n² log n) time, O(n) space)

Instead of sorting every time, maintain two heaps while expanding the subarray: a min-heap for elements inside the window and a max-heap for elements outside it. The smallest inside element represents the best candidate to swap out, while the largest outside element represents the best candidate to swap in. Perform up to k beneficial swaps where the outside value is greater. Heap operations reduce repeated sorting overhead and model the greedy insight: always replace the worst element in the subarray with the best available outside value.

Approach 3: Sliding Window with Dynamic Candidate Heaps (O(n log n) time, O(n) space)

The optimal strategy maintains the current window and dynamically tracks swap candidates using priority queues. Keep a min-heap of the smallest elements inside the window and a max-heap of the largest elements outside. As the window expands or shrinks, update heap membership using lazy deletion. For the current window, compute the best improvement by selecting up to k profitable swaps between the two heaps. This avoids rebuilding structures for every subarray and reduces the complexity to roughly O(n log n). The core idea is greedy replacement combined with efficient window maintenance.

Conceptually this problem combines greedy decisions with heap-based candidate tracking from priority queues. Efficient window traversal also resembles patterns used in sliding window problems.

Recommended for interviews: Start by explaining the brute force idea of checking every subarray and swapping the smallest inside elements with the largest outside elements. Then move to the heap-based optimization. Interviewers expect you to recognize the greedy swap rule and use heaps to efficiently track candidates, bringing the solution down to roughly O(n log n).