Home » Technical Interview Questions » Array Interview Questions » Maximum Sum of 3 Non-Overlapping Subarrays

Maximum Sum of 3 Non-Overlapping Subarrays


Reading Time - 9 mins

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.

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}

READ  Missing Number

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 of 3 Non-Overlapping Subarrays

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)

READ  Distinct adjacent elements in an array

where n is the number of elements present in the given array.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions