689. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution

In this guide, you will get 689. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution with the best time and space complexity. The solution to Maximum Sum of Non-Overlapping Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Sum of Non-Overlapping Subarrays solution in C++
4. Maximum Sum of Non-Overlapping Subarrays solution in Java
5. Maximum Sum of Non-Overlapping Subarrays solution in Python
6. Additional Resources

Problem Statement of Maximum Sum of Non-Overlapping Subarrays

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)

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

689. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution in C++

class Solution {
 public:
  vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    const int n = nums.size() - k + 1;
    // sums[i] := sum(nums[i..i + k))
    vector<int> sums(n);
    // l[i] := the index in [0..i] that has the maximum sums[i]
    vector<int> l(n);
    // r[i] := the index in [i..n) that has the maximum sums[i]
    vector<int> r(n);

    int sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
      sum += nums[i];
      if (i >= k)
        sum -= nums[i - k];
      if (i >= k - 1)
        sums[i - k + 1] = sum;
    }

    int maxIndex = 0;
    for (int i = 0; i < n; ++i) {
      if (sums[i] > sums[maxIndex])
        maxIndex = i;
      l[i] = maxIndex;
    }

    maxIndex = n - 1;
    for (int i = n - 1; i >= 0; --i) {
      if (sums[i] >= sums[maxIndex])
        maxIndex = i;
      r[i] = maxIndex;
    }

    vector<int> ans{-1, -1, -1};

    for (int i = k; i < n - k; ++i)
      if (ans[0] == -1 || sums[ans[0]] + sums[ans[1]] + sums[ans[2]] <
                              sums[l[i - k]] + sums[i] + sums[r[i + k]]) {
        ans[0] = l[i - k];
        ans[1] = i;
        ans[2] = r[i + k];
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

689. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution in Java

class Solution {
  public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
    final int n = nums.length - k + 1;
    // sums[i] := sum(nums[i..i + k))
    int[] sums = new int[n];
    // l[i] := the index in [0..i] that has the maximum sums[i]
    int[] l = new int[n];
    // r[i] := the index in [i..n) that has the maximum sums[i]
    int[] r = new int[n];

    int sum = 0;
    for (int i = 0; i < nums.length; ++i) {
      sum += nums[i];
      if (i >= k)
        sum -= nums[i - k];
      if (i >= k - 1)
        sums[i - k + 1] = sum;
    }

    int maxIndex = 0;
    for (int i = 0; i < n; ++i) {
      if (sums[i] > sums[maxIndex])
        maxIndex = i;
      l[i] = maxIndex;
    }

    maxIndex = n - 1;
    for (int i = n - 1; i >= 0; --i) {
      if (sums[i] >= sums[maxIndex])
        maxIndex = i;
      r[i] = maxIndex;
    }

    int[] ans = {-1, -1, -1};

    for (int i = k; i + k < n; ++i)
      if (ans[0] == -1 ||
          sums[ans[0]] + sums[ans[1]] + sums[ans[2]] < sums[l[i - k]] + sums[i] + sums[r[i + k]]) {
        ans[0] = l[i - k];
        ans[1] = i;
        ans[2] = r[i + k];
      }

    return ans;
  }
}
// code provided by PROGIEZ

689. Maximum Sum of 3 Non-Overlapping Subarrays LeetCode Solution in Python

class Solution:
  def maxSumOfThreeSubarrays(self, nums: list[int], k: int) -> list[int]:
    n = len(nums) - k + 1
    # sums[i] := sum(nums[i..i + k))
    sums = [0] * n
    # l[i] := the index in [0..i] that has the maximum sums[i]
    l = [0] * n
    # r[i] := the index in [i..n) that has the maximum sums[i]
    r = [0] * n

    summ = 0
    for i, num in enumerate(nums):
      summ += num
      if i >= k:
        summ -= nums[i - k]
      if i >= k - 1:
        sums[i - k + 1] = summ

    maxIndex = 0
    for i in range(n):
      if sums[i] > sums[maxIndex]:
        maxIndex = i
      l[i] = maxIndex

    maxIndex = n - 1
    for i in range(n - 1, -1, -1):
      if sums[i] >= sums[maxIndex]:
        maxIndex = i
      r[i] = maxIndex

    ans = [-1, -1, -1]

    for i in range(k, n - k):
      if (ans[0] == -1 or
          sums[ans[0]] + sums[ans[1]] + sums[ans[2]] <
              sums[l[i - k]] + sums[i] + sums[r[i + k]]):
        ans[0] = l[i - k]
        ans[1] = i
        ans[2] = r[i + k]

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.