Maximum Sum of Non-overlapping Subarrays

January 20, 2024

Problem #

Given an array nums and an integer k, find the maximum sum of non-overlapping subarrays, each of size k.

Example:

1. Input: nums = [1, 2, 3, 4, 5, 6, 1], k = 2 Output: 15 Explanation: The maximum sum is obtained by taking subarrays [5, 6] and [3, 4], which sum to 11 and 4 respectively. The total is 15.

Solution Approach #

The solution involves using a sliding window approach to find the maximum sum of each subarray of size k, and dynamic programming to ensure non-overlapping.

Algorithm Steps #

1. Use a sliding window to calculate the sum of every subarray of size k.
2. Use dynamic programming to store the maximum sum of non-overlapping subarrays up to the current index.
3. Iterate through the array and update the dynamic programming array.
4. Return the maximum value from the dynamic programming array.

Code (Python) #

def maxSumTwoNoOverlap(nums, k):
    n = len(nums)
    max_sum = [0] * n
    window_sum = sum(nums[:k])
    max_sum[k - 1] = window_sum

    # Sliding window for each subarray of size k
    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]
        max_sum[i] = max(max_sum[i - 1], window_sum)

    # Dynamic programming for non-overlapping subarrays
    for i in range(k, n):
        max_sum[i] = max(max_sum[i], max_sum[i - k] + sum(nums[i - k + 1:i + 1]))

    return max(max_sum)

# Test the function
print(maxSumTwoNoOverlap([1, 2, 3, 4, 5, 6, 1], 2))  # Output: 15

Time Complexity #

O(n), where n is the length of nums. Each element is processed once.

Space Complexity #

O(n), for the dynamic programming array.