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

# 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.

.wp-block-code {
border: 0;
}

.wp-block-code > div {
overflow: auto;
}

.hljs {
box-sizing: border-box;
}

.hljs.shcb-code-table {
display: table;
width: 100%;
}

.hljs.shcb-code-table > .shcb-loc {
color: inherit;
display: table-row;
width: 100%;
}

.hljs.shcb-code-table .shcb-loc > span {
display: table-cell;
}

.wp-block-code code.hljs:not(.shcb-wrap-lines) {
white-space: pre;
}

.wp-block-code code.hljs.shcb-wrap-lines {
white-space: pre-wrap;
}

.hljs.shcb-line-numbers {
border-spacing: 0;
counter-reset: line;
}

.hljs.shcb-line-numbers > .shcb-loc {
counter-increment: line;
}

.hljs.shcb-line-numbers .shcb-loc > span {
}

.hljs.shcb-line-numbers .shcb-loc::before {
border-right: 1px solid #ddd;
content: counter(line);
display: table-cell;
text-align: right;
-webkit-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
white-space: nowrap;
width: 1%;
}
.hljs > mark.shcb-loc { background-color: #ddf6ff; }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

#### You may also like July 20, 2020 - 12:57

can you please make a video of this explanation if possible? 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. 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 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. 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. 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] June 21, 2020 - 03:58

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

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