In the maximum sum of 3 non-overlapping subarrays problem we have given an array nums of positive integers, find three non-overlapping subarrays of length k with a maximum sum, and return their starting indices.
Table of Contents
Example
Input:
nums[] = {1, 2, 1, 2, 6, 7, 5, 1}
k = 2
Output:
{0, 3, 5}
Algorithm for Maximum Sum of 3 Non-Overlapping Subarrays
The idea is to build a sum array that stores the sum of all k length continuous subarrays. For index i, the maximum sum obtained from it is sum[i] + maximum value of sum from index 0 to (i -k) + maximum value of sum from the index (i + k) to length of the sum.
Create 2 more arrays left and right, where, left stores the index of maximum sum of a contiguous array of length k up to that index and right also stores the same but starting from the end.
Traverse the array sum starting from index k to index (length of sum – k), for each index i, the maximum sum obtained from it is sum[i] + sum[left[i – k]] + sum[right[i + k]].
For all the possible sums, find the maximum sum and their corresponding indices.
Explanation for Maximum Sum of 3 Non-Overlapping Subarrays
Consider the array in the example above,
nums[] = {1, 2, 1, 2, 6, 7, 5, 1} and k = 2
For the nums array build sum array that stores all the possible sums of contiguous subarrays of length 2.
sum[] = {3, 3, 3, 8, 13, 12, 6}
Create arrays left and right as described in the algorithm
left[] = {0, 0, 0, 3, 4, 4, 4}
right[] = {4, 4, 4, 4, 4, 5, 6}
Traverse in the sum array starting from index 2 to index 4,
- i = 2, sum[i] = 3
sum obtained from index 2 = 3 + (sum[left[2 – 2]]) + (sum[right[2 + 2]]) = 19 - i = 3, sum[i] = 8
sum obtained from index 3 = 8 + (sum[left[3 – 2]]) + (sum[right[3 + 2]]) = 23 - i = 4, sum[i] = 13
sum obtained from index 4 = 13 + (sum[left[4 – 2]]) + (sum[right[4 + 2]]) = 22
Maximum sum obtained = 23 and starting indices are {0, 3, 5}
JAVA Code for Maximum Sum of 3 Non-Overlapping Subarrays
public class MaximumSumOfThreeNonOverlappingIntervals {
private static int[] findInicies(int[] nums, int k) {
int n = nums.length;
// build sum array that stores the sum of all k length continuous subarrays
int sum[] = new int[n - k + 1];
int currSum = 0;
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
sum[0] = currSum;
for (int i = k;i < n; i++) {
currSum -= nums[i - k];
currSum += nums[i];
sum[i - k + 1] = currSum;
}
// Create left array that stores the index of maximum sum of contiguous array of length k upto that index
int left[] = new int[sum.length];
int best = 0;
for (int i = 0; i < sum.length; i++) {
if (sum[i] > sum[best]) {
best = i;
}
left[i] = best;
}
best = sum.length - 1;
// Create right array that stores the index of maximum sum of contiguous array of length k upto that index
// starting from end
int right[] = new int[sum.length];
for (int i = sum.length - 1; i >= 0; i--) {
if (sum[i] >= sum[best]) {
best = i;
}
right[i] = best;
}
// Initialise ans array as -1
int ans[] = new int[] {-1, -1, -1};
// Traverse in sum array from index k to (sum length - k)
for (int i = k; i < sum.length - k; i++) {
// Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
int l = left[i - k];
int r = right[i + k];
if (ans[0] == -1 ||
(sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
// Update the indices if the max sum is greater than the actual max sum
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}
// return ans array
return ans;
}
public static void main(String[] args) {
// Example
int nums[] = new int[] {1,2,1,2,6,7,5,1};
int k = 2;
int indices[] = findInicies(nums, k);
for (int i = 0; i < 3; i++)
System.out.print(indices[i] + " ");
System.out.println();
}
}C++ Code for Maximum Sum of 3 Non-Overlapping Subarrays
#include <iostream>
#include <vector>
using namespace std;
void findIndices(int *nums, int k, int n, vector<int> &ans) {
// build sum array that stores the sum of all k length continuous subarrays
int sum[n- k + 1];
int currSum = 0;
for (int i = 0; i < k; i++) {
currSum += nums[i];
}
sum[0] = currSum;
for (int i = k;i < n; i++) {
currSum -= nums[i - k];
currSum += nums[i];
sum[i - k + 1] = currSum;
}
// Create left array that stores the index of maximum sum of contiguous array of length k upto that index
int left[n - k + 1];
int best = 0;
for (int i = 0; i < n - k + 1; i++) {
if (sum[i] > sum[best]) {
best = i;
}
left[i] = best;
}
best = n - k;
// Create right array that stores the index of maximum sum of contiguous array of length k upto that index
// starting from end
int right[n - k + 1];
for (int i = n - k; i >= 0; i--) {
if (sum[i] >= sum[best]) {
best = i;
}
right[i] = best;
}
// Initialise ans array as -1
ans.push_back(-1);
ans.push_back(-1);
ans.push_back(-1);
// Traverse in sum array from index k to (sum length - k)
for (int i = k; i < (n - k + 1 - k); i++) {
// Maximum sum obtained from this index is sum[i] + sum[left[i -k]] + sum[right[i + k]]
int l = left[i - k];
int r = right[i + k];
if (ans[0] == -1 ||
(sum[l] + sum[i] + sum[r]) > (sum[ans[0]] + sum[ans[1]] + sum[ans[2]])) {
// Update the indices if the max sum is greater than the actual max sum
ans[0] = l;
ans[1] = i;
ans[2] = r;
}
}
}
int main() {
int nums[] = {1,2,1,2,6,7,5,1};
int k = 2;
int n = sizeof(nums) / sizeof(nums[0]);
vector<int> ans;
findIndices(nums, k, n, ans);
for (int i = 0; i < ans.size(); i++) {
cout<<ans[i]<<" ";
}
cout<<endl;
return 0;
}0 3 5
Complexity Analysis
Time Complexity = O(n)
Space Complexity = O(n)
where n is the number of elements present in the given array.