Brute Force Approach

A naive approach would involve iterating through all possible combinations of three non-overlapping subarrays of length k and computing their sums. We can then find the combination that yields the maximum sum and return the starting indices. This approach is simple to understand but highly inefficient.

def max_sum_three_subarrays_brute_force(nums, k):
    n = len(nums)
    max_sum = 0
    result = []

    for i in range(n - 3 * k + 1):
        for j in range(i + k, n - 2 * k + 1):
            for l in range(j + k, n - k + 1):
                sum1 = sum(nums[i:i+k])
                sum2 = sum(nums[j:j+k])
                sum3 = sum(nums[l:l+k])
                current_sum = sum1 + sum2 + sum3

                if current_sum > max_sum:
                    max_sum = current_sum
                    result = [i, j, l]

    return result

Time Complexity: O(n^3), where n is the length of the input array nums.

Space Complexity: O(1), as we only use a constant amount of extra space.

Optimal Solution: Sliding Window with Dynamic Programming

To improve efficiency, we can use a sliding window technique combined with dynamic programming to precompute the maximum sum subarrays from left to right and from right to left. This helps us to find the optimal solution in linear time.

1. Prefix Sums: Calculate the prefix sums to efficiently compute the sum of each subarray of length k.
2. Left DP: Create a left array where left[i] stores the starting index of the maximum sum subarray of length k in nums[0...i].
3. Right DP: Create a right array where right[i] stores the starting index of the maximum sum subarray of length k in nums[i...n-1].
4. Iterate and Find Max: Iterate through the possible middle subarray starting positions. For each middle subarray starting at index j, we find the maximum sum by combining the maximum sum subarray to its left (using left[j-k]), the sum of the middle subarray, and the maximum sum subarray to its right (using right[j+k]).
5. Lexicographically Smallest: When we encounter multiple answers with the same maximum sum, we select the lexicographically smallest one by updating our result only when we find a strictly greater sum.

def max_sum_three_subarrays(nums, k):
    n = len(nums)
    sums = []
    window_sum = sum(nums[:k])
    sums.append(window_sum)

    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]
        sums.append(window_sum)

    left = [0] * n
    best = 0
    for i in range(k, n - 2 * k + 1):
        if sums[i] > sums[best]:
            best = i
        left[i] = best

    right = [0] * n
    best = n - k
    for i in range(n - k - 1, 2 * k - 1, -1):
        if sums[i] >= sums[best]:
            best = i
        right[i] = best

    max_sum = 0
    result = []

    for j in range(k, n - 2 * k + 1):
        left_index = left[j - k]
        right_index = right[j + k]
        current_sum = sums[left_index] + sums[j] + sums[right_index]

        if current_sum > max_sum:
            max_sum = current_sum
            result = [left_index, j, right_index]

    return result

Time Complexity: O(n), where n is the length of the input array nums.

Space Complexity: O(n), due to the use of the left, right, and sums arrays.

Edge Cases

• Empty Array: If the input array is empty, there are no subarrays, and we should return an appropriate error message or an empty list.
• k > n/3: If k is larger than one-third of the array's length, there are no three non-overlapping subarrays of length k, and again we return an appropriate error message or empty list. The problem statement specifies 1 <= k <= floor(nums.length / 3). So you should not need to test this case in an interview.
• Multiple Answers: If there are multiple sets of subarrays that produce the same maximum sum, the problem requires returning the lexicographically smallest one. Our algorithm already handles this.

Example

nums = [1, 2, 1, 2, 6, 7, 5, 1]
k = 2
print(max_sum_three_subarrays(nums, k))  # Output: [0, 3, 5]

nums = [1, 2, 1, 2, 1, 2, 1, 2, 1]
k = 2
print(max_sum_three_subarrays(nums, k))  # Output: [0, 2, 4]