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 > span {
display: block;
overflow: auto;
}

.shcb-language {
border: 0;
clip: rect(1px, 1px, 1px, 1px);
-webkit-clip-path: inset(50%);
clip-path: inset(50%);
height: 1px;
margin: -1px;
overflow: hidden;
position: absolute;
width: 1px;
word-wrap: normal;
word-break: normal;
}

.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;
}
Code language: Java (java)

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. :)