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  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`

1031. Maximum Sum of Two Non-Overlapping Subarrays
``````struct Solution;

use std::i32;

impl Solution {
fn max_sum_two_no_overlap(mut a: Vec<i32>, l: i32, m: i32) -> i32 {
let n = a.len();
let l = l as usize;
let m = m as usize;
for i in 1..n {
a[i] += a[i - 1];
}
let mut res = a[l + m - 1];
let mut max_l = a[l - 1];
let mut max_m = a[m - 1];
for i in l + m..n {
max_l = i32::max(a[i - m] - a[i - m - l], max_l);
max_m = i32::max(a[i - l] - a[i - l - m], max_m);
let last_l = a[i] - a[i - l];
let last_m = a[i] - a[i - m];
res = i32::max(i32::max(max_m + last_l, max_l + last_m), res);
}
res
}
}

#[test]
fn test() {
let a = vec![0, 6, 5, 2, 2, 5, 1, 9, 4];
let l = 1;
let m = 2;
let res = 20;
assert_eq!(Solution::max_sum_two_no_overlap(a, l, m), res);
let a = vec![3, 8, 1, 3, 2, 1, 8, 9, 0];
let l = 3;
let m = 2;
let res = 29;
assert_eq!(Solution::max_sum_two_no_overlap(a, l, m), res);
let a = vec![2, 1, 5, 6, 0, 9, 5, 0, 3, 8];
let l = 4;
let m = 3;
let res = 31;
assert_eq!(Solution::max_sum_two_no_overlap(a, l, m), res);
}
``````