Introduction

In this blog post, we will explore how to solve the LeetCode problem "689" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them. Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one. Example 1: Input: nums = [1,2,1,2,6,7,5,1], k = 2 Output: [0,3,5] Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5]. We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically smaller. Example 2: Input: nums = [1,2,1,2,1,2,1,2,1], k = 2 Output: [0,2,4] Constraints: 1 <= nums.length <= 2 * 104 1 <= nums[i] < 216 1 <= k <= floor(nums.length / 3)

Explanation

Here's the solution to the problem, incorporating efficiency and adhering to the specified constraints:

• Prefix Sum and Window Sum Calculation: Use prefix sums to efficiently compute the sum of each subarray of length k in O(1) time.
• Dynamic Programming for Optimal Left and Right Subarrays: Utilize dynamic programming to find the optimal starting indices for the leftmost and rightmost subarrays for any given middle subarray. This avoids redundant calculations.

• Iterate and Maximize: Iterate through possible middle subarray starting positions and combine the optimal left, middle, and right subarrays to find the combination with the maximum sum, prioritizing lexicographically smaller results.

• Runtime Complexity: O(n) , Storage Complexity: O(n)

Code

    def max_sum_three_non_overlapping_subarrays(nums, k):
    n = len(nums)
    sums = [0] * (n - k + 1)
    window_sum = sum(nums[:k])
    sums[0] = window_sum
    for i in range(k, n):
        window_sum += nums[i] - nums[i - k]
        sums[i - k + 1] = window_sum

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

    right = [0] * (n - k + 1)
    best = n - k
    for i in range(n - k, -1, -1):
        if sums[i] >= sums[best]:  # >= to prioritize smaller indices
            best = i
        right[i] = best

    ans = None
    max_sum = 0
    for j in range(k, n - 2 * k + 1):
        l = left[j - k]
        r = right[j + k]
        current_sum = sums[l] + sums[j] + sums[r]

        if current_sum > max_sum:
            max_sum = current_sum
            ans = [l, j, r]

    return ans