Maximize Maximum Subarray Sum with K Swaps

Given an integer array a of length n and an integer k, you may perform exactly k swaps. Each swap chooses two indices i and j and exchanges a[i] and a[j]. You may swap the same pair more than once; a repeated swap can cancel a previous one, so the effective number of useful swaps is at most k.

Return the maximum possible maximum subarray sum achievable after performing the swaps.

A subarray must be non-empty.

Write a function max_subarray_sum_after_k_swaps(a: list[int], k: int) -> int.

Examples:

1. a = [5, -1, 5], k = 0
   The maximum subarray sum is 9.

2. a = [-2, 3, -1, 2], k = 1
   By swapping -2 with 2, the array can become [2, 3, -1, -2], whose maximum subarray sum is 5.

Constraints:

• 2 <= n <= 500
• 0 <= k <= n
• -1000 <= a[i] <= 1000

Notes:

• If no swap improves the answer, the best arrangement may be the original array.
• Swapping an element with itself is allowed but has no effect.