# 1031. Maximum Sum of Two Non-Overlapping Subarrays

Given an array `A` of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths `L` and `M`.  (For clarification, the `L`-length subarray could occur before or after the `M`-length subarray.)

Formally, 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])` and either:

• `0 <= i < i + L - 1 < j < j + M - 1 < A.length`or
• `0 <= j < j + M - 1 < i < i + L - 1 < A.length`.

Example 1:

Input:

```A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
```

Output:

```20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.
```

Example 2:

Input:

```A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
```

Output:

```29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.
```

Example 3:

Input:

```A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
```

Output:

```31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.
```

Note:

1. `L >= 1`
2. `M >= 1`
3. `L + M <= A.length <= 1000`
4. `0 <= A[i] <= 1000`
```class Solution {

/**
* @param Integer[] \$A
* @param Integer \$L
* @param Integer \$M
* @return Integer
*/
function maxSumTwoNoOverlap(\$A, \$L, \$M) {
\$max  = 0;
\$a = [];
\$b = [];
for(\$i  = 0; \$i < count(\$A)-\$L+1; \$i ++){
\$a[\$i] =  array_sum(array_slice(\$A,\$i,\$L));
}

for(\$j = 0; \$j < count(\$A)-\$M+1; \$j ++){
\$b[\$j] = array_sum(array_slice(\$A,\$j,\$M));
}
arsort(\$a);arsort(\$b);
foreach(\$a as \$ak => \$av){
foreach(\$b as \$bk => \$bv){
if(\$bk + \$M <= \$ak || \$ak + \$L <= \$bk){
\$max = max(\$max, \$av + \$bv);

}
}
}

return \$max;
}
}```

160ms

#### Thoughts:

• My code is the version used for contest, so..
• The length of inputs (1000) seems relatively small, so just follow your heart, again…
• Idea, scan & store sums for L &  M fixed size arrays.
• for each sum L and for each sum M, if no overlap, the check and update max total.
• What makes it slow:
• array_sum.. fixed size sliding door works better, but more codes…
• double for each, there’s an obvious pattern to move index out of overlap.
• Having these sorts have 10ms improvement, which is quite interesting.

#### Improved Version

```class Solution {

/**
* @param Integer[] \$A
* @param Integer \$L
* @param Integer \$M
* @return Integer
*/
function maxSumTwoNoOverlap(\$A, \$L, \$M) {
\$max  = 0;
\$a = [];
\$b = [];

for(\$i  = 0; \$i < count(\$A)-\$L+1; \$i ++){
if(\$i == 0){
\$a[\$i] =  array_sum(array_slice(\$A,\$i,\$L));
} else {
\$a[\$i] = \$a[\$i-1] - \$A[\$i-1] + \$A[\$i+\$L-1];
}
}

for(\$i = 0; \$i < count(\$A)-\$M+1; \$i ++){
if(\$i == 0){
\$b[\$i] =  array_sum(array_slice(\$A,\$i,\$M));
} else {
\$b[\$i] = \$b[\$i-1] - \$A[\$i-1] + \$A[\$i+\$M-1];
}
}
for(\$i = 0; \$i < count(\$a); \$i++){
for(\$j = 0; \$j < count(\$b);\$j++){
if(\$j + \$M <= \$i || \$i + \$L <= \$j){
\$max = max(\$max, \$a[\$i] + \$b[\$j]);
} else if(\$j + \$M <= \$i){
\$j += (\$M-1);
}
}
}

return \$max;
}
}```
• The “fixed size sliding door” saved about 20ms
• No significant improvement for the double for each.