Daily Coding Challenge #90: Arrays (Hard)

Tuesday, March 31, 2026 — Hard difficulty — Topic: Arrays

Problem Title: "Maximum Subarray Sum After M Operations"

Problem Statement:

You are given an array of integers nums and two integers k and m. You can perform m operations on the array, where each operation consists of selecting a subarray and flipping the sign of all its elements. The goal is to find the maximum possible sum of the array after performing m operations.

Examples:

1. nums = [1, -2, 3, -4, 5], k = 3, m = 2
   Output: 15
   Explanation: We can flip the signs of the subarrays [-2, 3, -4] and [5] to get [1, 2, 3, 4, 5], which has a sum of 15.

2. nums = [-1, -2, -3, -4, -5], k = 3, m = 2
   Output: 5
   Explanation: We can flip the signs of the subarrays [-1, -2, -3] and [-4, -5] to get [1, 2, 3, -4, -5], which has a sum of 5. Note that we cannot flip the entire array because m = 2, which is less than the number of negative numbers.

3. nums = [1, 2, 3, 4, 5], k = 3, m = 0
   Output: 15
   Explanation: Since m = 0, we cannot flip any subarrays, so the sum remains the same.

Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 1 <= k <= 10^5
• 0 <= m <= 10^5
• Time complexity: O(n log n)
• Space complexity: O(n)

Hints:

1. Think about how you can use a priority queue to keep track of the m smallest subarrays in the array.
2. Consider using a prefix sum array to efficiently calculate the sum of subarrays.

Solution Walkthrough:

1. Initialize a prefix sum array prefix of size n + 1, where prefix[i] is the sum of the first i elements of nums.
2. Initialize a priority queue pq to store the sums of subarrays.
3. Iterate through the array and for each element, calculate the sum of the subarray ending at that element using the prefix sum array.
4. Push the sum of the subarray into the priority queue.
5. After iterating through the entire array, pop the m smallest sums from the priority queue and flip the signs of the corresponding subarrays.
6. Calculate the sum of the array after flipping the signs of the subarrays.

Python Solution:

import heapq

def maxSubarraySumAfterMOperations(nums, k, m):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    pq = []
    for i in range(n):
        for j in range(i + 1, min(i + k + 1, n + 1)):
            subarray_sum = prefix[j] - prefix[i]
            heapq.heappush(pq, subarray_sum)
            if len(pq) > m:
                heapq.heappop(pq)

    result = 0
    while pq:
        result += -heapq.heappop(pq)
    result += prefix[n]
    return result

JavaScript Solution:

function maxSubarraySumAfterMOperations(nums, k, m) {
    let n = nums.length;
    let prefix = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + nums[i];
    }

    let pq = [];
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j <= Math.min(i + k, n); j++) {
            let subarraySum = prefix[j] - prefix[i];
            pq.push(subarraySum);
            pq.sort((a, b) => a - b);
            if (pq.length > m) {
                pq.shift();
            }
        }
    }

    let result = 0;
    while (pq.length > 0) {
        result += -pq.shift();
    }
    result += prefix[n];
    return result;
}

Time/Space Complexity Analysis:

• Time complexity: O(n log n) due to the use of a priority queue and sorting.
• Space complexity: O(n) due to the use of a prefix sum array and a priority queue.

Follow-up Challenge:

"Maximum Subarray Sum After M Operations with Constraints"

• Add a constraint that each subarray can only be flipped at most once.
• Modify the solution to keep track of the number of times each subarray has been flipped.

Find this helpful? Follow for daily coding challenges!