LeetCode 689: Maximum Sum of 3 Non-Overlapping Subarrays Solution
Master LeetCode problem 689 (Maximum Sum of 3 Non-Overlapping Subarrays), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
689. Maximum Sum of 3 Non-Overlapping Subarrays
Problem Explanation
Explanation:
To solve this problem, we can use dynamic programming. We first calculate the sum of every possible non-overlapping subarray of length k in the input array nums. Then we iterate through the array to find the maximum sum of two non-overlapping subarrays that end at index i and start at index i + 1. By keeping track of the maximum sum found so far, we can determine the starting indices of the three non-overlapping subarrays with the maximum sum.
Here are the steps:
- Calculate the cumulative sum of nums in a separate array.
- Calculate the sum of every non-overlapping subarray of length k.
- Initialize two arrays to store the maximum sum of two non-overlapping subarrays that end at index i and start at index i + 1.
- Iterate through the array to find the maximum sum and the corresponding starting indices.
- Return the starting indices of the three non-overlapping subarrays with the maximum sum.
Time complexity: O(n), where n is the length of the input array nums. Space complexity: O(n) for storing cumulative sums and intermediate results.
:
Solution Code
class Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int n = nums.length;
int[] sum = new int[n + 1];
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + nums[i];
}
int[] leftMax = new int[n];
int[] rightMax = new int[n];
int[] leftIndex = new int[n];
int[] rightIndex = new int[n];
int total = sum[k] - sum[0];
for (int i = k; i < n; i++) {
if (sum[i + 1] - sum[i + 1 - k] > total) {
leftMax[i] = sum[i + 1] - sum[i + 1 - k];
leftIndex[i] = i + 1 - k;
total = sum[i + 1] - sum[i + 1 - k];
} else {
leftMax[i] = total;
leftIndex[i] = i - k + 1;
}
}
total = sum[n] - sum[n - k];
rightMax[n - k] = total;
rightIndex[n - k] = n - k;
for (int i = n - k - 1; i >= 0; i--) {
if (sum[i + k] - sum[i] >= total) {
rightMax[i] = sum[i + k] - sum[i];
rightIndex[i] = i;
total = sum[i + k] - sum[i];
} else {
rightMax[i] = total;
rightIndex[i] = rightIndex[i + 1];
}
}
int maxSum = 0;
int[] result = new int[3];
for (int i = k; i <= n - 2 * k; i++) {
int left = leftMax[i - 1];
int right = rightMax[i + k];
int totalSum = sum[i + k] - sum[i] + left + right;
if (totalSum > maxSum) {
maxSum = totalSum;
result[0] = leftIndex[i - 1];
result[1] = i;
result[2] = rightIndex[i + k];
}
}
return result;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 689 (Maximum Sum of 3 Non-Overlapping Subarrays)?
This page provides optimized solutions for LeetCode problem 689 (Maximum Sum of 3 Non-Overlapping Subarrays) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 689 (Maximum Sum of 3 Non-Overlapping Subarrays)?
The time complexity for LeetCode 689 (Maximum Sum of 3 Non-Overlapping Subarrays) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 689 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 689 in Java, C++, or Python.