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

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

by nikoo28
7 comments

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; }

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

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

7 comments

You may also like

7 comments

J July 20, 2020 - 12:57

can you please make a video of this explanation if possible?

Reply
nikoo28 August 3, 2020 - 21:49

I will get to it in some time. Till then can you describe confusion you faced? I will try to clear it out.

Reply
hago July 19, 2020 - 11:08

Hi,
Can you please explain why is the for loop starting from i = L + M? and the for loop in more detail?

Thanks
hago

Reply
nikoo28 July 19, 2020 - 15:24

Hi hago,

TLDR: It is a starting point for the loop.

If you have a close look at the prefix sum array, you will get your answer.
It is a cumulative sum of all the elements in the array.

So, if the array L is of size 3, and array M is of size 2. You know the cumulative sum of (L + M = 5) elements. This is your starting point of the loop.

The problem requires a sum of 2 contiguous sub-arrays. We need a starting point/default answer to begin our calculations, and for this problem we assume that the first 5 elements were forming the maximum sum.

We need to proceed further from those first elements. That should explain why we start our loop at L+M.

Reply
nikoo28 July 19, 2020 - 15:31

For part 2 of your question, what does the for loop do.

We defined 2 arrays L of size 3, and M of size 2. The total length is 5, but we don’t know yet how will we get the largest sum.
We are faced with 2 conditions:

  • – The first 3 elements (1,2,3) form array L.
  • – Elements (3,4,5) form the array L.

In order to get the maximum answer, we try to consider both the possibilities.

Reply
Udi June 19, 2020 - 08:09

This is a great explanation. I’d like point out 1 small typo: in the comment # M before L: A[i – M] …, it should be #M before L: A[i – L]

Reply
nikoo28 June 21, 2020 - 03:58

Thanks for the feedback. I updated the post. :)

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More