https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/

MaximumSumOfTwoNon-OverlappingSubarrays.js

/**
 * @param {number[]} A
 * @param {number} L
 * @param {number} M
 * @return {number}
 */

/*
Brute Force: O((n-L)(n-M))
Idea: For each possible window of size L, find
the maximum window of size M to the left and right
of it.
*/
var maxSumTwoNoOverlap = function(A, L, M) {
    
    // use cumulative sums to get the sum of a window in O(1)
    const cumulative = new Array(A.length).fill(A[0]);
    for(let i=1; i<A.length; i++){
        cumulative[i] = cumulative[i-1] + A[i];
    }
    
    let lSum = A.slice(0, L).reduce((a, b) => a + b); // initialise window L
    let mSum = Math.max(maxSumFrom(L)); // initialise window M
    let result=lSum+mSum; // track the result
    
    for(let i=L; i<A.length; i++){ // for every window L
        lSum = lSum + A[i] - A[i-L]; // add the sum of that window
        mSum = Math.max(maxSumFrom(i+1),maxSumTo(i-L)); // to the max corresponding window M on either side
        result = Math.max(result, lSum + mSum);
    }
    
    return result;
    
    function maxSumFrom(i){
        let result = -Infinity;
        for(let k=i; k<A.length; k++){
            const endIndex = k+M-1;
            if(endIndex >= A.length) continue;;
            result = Math.max(cumulative[endIndex] - cumulative[k-1], result);
        }
        
        return result;
    }
    
    function maxSumTo(i){
        let result = -Infinity;
        for(let k=0; k<=i; k++){
            const startIndex = k-M+1;
            if(startIndex < 0) continue;;
            result = Math.max(result,cumulative[k] - (cumulative[startIndex-1] || 0));
        }
        return result;
    }
};

/*
O(n)
Idea 1: There are two cases. L is before M, or L is after M.
Idea 2: work out the answer for these two cases separately.

ASSUMING: L is before M:
- We can work out the maximim window of size L ending at or
  before index i in a single pass. 
- If we track the max of the sum of these two two variables for each i:
  - maxLWindowEndingAtOrBeforeI
  - mWindowStartingAtIPlusOne
  we'll have out answer.

- Another way of saying the same thing:
  - For every possible window M, right of L, track the maximum
    window of size L to the left of it. 

Now break that assumption and assume the opposite:
- For every possible window M, left of L, track the maximum
    window of size M to the right of it. 
*/
var maxSumTwoNoOverlap = function(A, L, M) {
    
    const cumulative = new Array(A.length).fill(A[0]);
    for(let i=1; i<A.length; i++) cumulative[i] = cumulative[i-1] + A[i];
    
    let [lSum, mSum, result] = [0, 0, 0];
    
    // if L is before M
    for(let i=L-1; i<A.length-M; i++){ // for every possible window of size M that fits L to the left of it
        mSum = cumulative[i+M] - cumulative[i]; // sum the window M
        lSum = Math.max(lSum, cumulative[i] - (cumulative[i-L]||0) ); // and remember the max L to the left of it
        result = Math.max(result, lSum + mSum); // if L is before M, the result will be this
    }
    
    // if M is before L
    [lSum, mSum] = [0, 0]; // reset L and M
    for(let i=A.length-1; i>=L+M-1; i--){ // for every possible window of size M that fits L to the right of it
        mSum = cumulative[i-L] - (cumulative[i-L-M]||0); // sum that window M
        lSum = Math.max(lSum, cumulative[i] - cumulative[i-L]); // and remember the max L to the right of it
        result = Math.max(result, lSum + mSum); // if L is *after* M, the result will be this
    }
    
    return result;
    
};