Largest Subarray Sum with a Limited Number of Swaps

# Largest Subarray Sum with a Limited Number of Swaps You are given an integer array `nums` and an integer `k`. You may perform at most `k` swaps. Each swap exchanges the elements at any two chosen indices; the indices do not need to be adjacent. After the swaps, choose a nonempty contiguous subarray. Return the largest possible sum of such a subarray, over every allowed sequence of swaps and every final choice of subarray. ### Function `long long maxSum(vector<int>& nums, int k)` ### Example 1 **Input:** `nums = [5, -9, 4, -8, 6], k = 1` **Output:** `15` **Explanation:** Swap indices `1` and `4` to obtain `[5, 6, 4, -8, -9]`. The first three elements sum to `15`. This is the sum of all positive values in the array, so no subarray after any swaps can have a larger sum. ### Example 2 **Input:** `nums = [-7, -2, -5], k = 2` **Output:** `-2` **Explanation:** Make no swaps and choose the singleton `[-2]`. Reordering negative values cannot make a nonempty subarray sum exceed the largest individual value, `-2`. ### Constraints - `1 <= nums.length <= 1500` - `-100000 <= nums[i] <= 100000` - `0 <= k <= nums.length` ### Clarifications - Using fewer than `k` swaps, including none, is allowed. - Swaps may involve positions inside or outside the eventual chosen subarray. - The subarray is nonempty even when every value is negative. - Return only the maximum sum; no sequence of swaps or interval endpoints is required. ### What a Strong Answer Covers - Optimizing both the swaps and the final contiguous interval. - Accounting for swaps between arbitrary positions without assuming they must be adjacent. - Handling duplicate values, unused swaps and all-negative inputs at the full length limit.