Maximum sum of elements in two non-overlapping contiguous sub arrays

Question: Given an array A, find the sum of maximum sum of two non-overlapping subarrays, with lengths L and M.
In other words, return the largest V for which V = (A[i] + A[i+1] …. A[i+L-1]) + (A[j] + A[j+1] …. A[j+M-1])
Input: A = {3, 8, 1, 3, 2, 1, 8, 9, 0}; L = 3, M = 2
Output: 29

The problem statement is quite clear.

• We need to find 2 contiguous sub-arrays from an array
• Add the elements of both these arrays
• The sum should be the maximum possible sum of all the possible sub array combinations.

In the given sample test case.
L = {3, 8, 1} and M = {8, 9}

The problem is a slight variation of finding the largest sum sub-array. In that problem we find only one sub-array with the maximum sum. So, with a little brain storming we can breakdown this problem basically into 2 sub problems.

• First find the maximum L-length sub-array. Let the sum be (X) Out of the remaining array, find the maximum M-length sub-array. Let the sum be (Y)
• Now find the maximum length M-length sub-array. Let the sum be (A). Out of the remaining array, find the maximum L-length sub-array. Let the sum be (B).
• The answer would be V = MAX ( (X + Y) , (A + B) )

The algorithm would be as follows.

public int maxSumTwoNoOverlap(int[] A, int L, int M) {

    // Construct prefix sum
    // This array contains sum of all contiguous elements
    for (int i = 1; i < A.length; i++) {
      A[i] = A[i - 1] + A[i];
    }

    // Assign initial values so we can skip 1st run in below for loop
    // Taking the default result to be the first L + M elements
    int res = A[L + M - 1];
    int maxL = A[L - 1];
    int maxM = A[M - 1];

    // Either L before M or M before L, start this loop at index L + M
    for (int i = L + M; i < A.length; i++) {

      // Keep track maxL so far
      // L before M: A[i - M] - A[i - M - L] is sum of L-length sub array
      maxL = Math.max(maxL, A[i - M] - A[i - M - L]);

      // Keep track maxM so far
      // M before L: A[i - L] - A[i - L - M] is sum of M-length sub array
      maxM = Math.max(maxM, A[i - L] - A[i - L - M]);

      // Keep track res so far
      // maxL + (A[i] - A[i - M]): Sum of max L-length sub array and current M-length sub array
      // maxM + (A[i] - A[i - L]): Sum of max M-length sub array and current L-length sub array
      res = Math.max(res, Math.max(maxL + (A[i] - A[i - M]), maxM + (A[i] - A[i - L])));
    }
    return res;
  }
Code language: Java (java)

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

A working solution can be found here. https://ideone.com/ZoZyrW