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:

L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000

Difficulty: interview

Starter code:

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        

Solutions:
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        N = len(A)
        if L+M>N:
            return -1


        def findmax(L,M):    
            sL = [sum(A[:L])]
            for i in range(L,N-M):
                tmp = sL[-1]+A[i]-A[i-L]
                sL.append(tmp)
            sLmax = [sL[0]]
            for i in range(1,len(sL)):
                if sL[i]>sLmax[-1]:
                    sLmax.append(sL[i])
                else:
                    sLmax.append(sLmax[-1])

            sM = [sum(A[-M:])]
            for i in range(N-M-1,L-1,-1):
                tmp = sM[-1]+A[i]-A[i+M]
                sM.append(tmp)
            sMmax = [sM[0]]
            for i in range(1,len(sM)):
                if sM[i]>sMmax[-1]:
                    sMmax.append(sM[i])
                else:
                    sMmax.append(sMmax[-1])

            sMax = [sum(x) for x in zip(sLmax, sMmax[::-1])]
            m = max(sMax)

            return m

        if L == M:
            return findmax(L,M)
        else:
            return max(findmax(L,M), findmax(M,L))

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix_sum = [0] * (len(A) + 1)
        for i in range(len(A)): prefix_sum[i+1] = prefix_sum[i] + A[i]
        maxM = maxL = result = 0
        
        for i in range(M, len(prefix_sum) - L):
            # optimal for L-list start at i+1 and occur after M-list
            maxM = max(maxM, prefix_sum[i] - prefix_sum[i-M])
            result = max(result, maxM + prefix_sum[i+L] - prefix_sum[i])
            
        for i in range(L, len(prefix_sum) - M):
            # optimal for M-list start at i+1 and occur after L-list
            maxL = max(maxL, prefix_sum[i] - prefix_sum[i-L])
            result = max(result, maxL + prefix_sum[i+M] - prefix_sum[i])
            
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        sub_L = [sum(A[i:i+L]) for i in range(len(A)-L+1)]
        sub_M = [sum(A[i:i+M]) for i in range(len(A)-M+1)]
        
        # let p be the index of sub_L, and q be the index of sub_M.
        # we require (q+M-1) - (p+L-1) >= M  or (p+L-1) - (q+M-1) >= L.
        # equivalently: q - p >= L or p - q >= M
        
        max_L_M = float('-inf')
        max_M_L = float('-inf')

        
        p, q = 0, L
        while q < len(sub_M):
            if sub_L[q-L] > sub_L[p]:
                p = q - L
            max_L_M = max(max_L_M, sub_M[q] + sub_L[p])
            q += 1
        
        q, p = 0, M
        while p < len(sub_L):
            if sub_M[p-M] > sub_M[q]:
                q = p - M
            max_M_L = max(max_M_L, sub_L[p] + sub_M[q])
            p += 1

        return max(max_L_M, max_M_L)

class Solution:
    def maxSumTwoNoOverlap(self, arr: List[int], L: int, M: int) -> int:
        
        n=len(arr)
        pre=[arr[0] for i in range(len(arr))]
        for j in range(1,n):
            pre[j]=pre[j-1]+arr[j]
            
        res1=-1   
        for i in range(n-(L+M)+1):
            for k in range(i+L,n-M+1):
                sum1=pre[i+L-1]-(pre[i-1] if i>0 else 0)
                sum2=pre[k+M-1]-(pre[k-1] if k>0 else 0)
                res1=max(res1,sum1+sum2)       
        res2=-1       
        for i in range(n-(L+M)+1):
            for k in range(i+M,n-L+1):
                sum1=pre[i+M-1]-(pre[i-1] if i>0 else 0)
                sum2=pre[k+L-1]-pre[k-1]
                res2=max(res2,sum1+sum2)
                
        return max(res1,res2)

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        S = [A[0]]
        for i in range(1,len(A)): S.append(S[-1] + A[i])
        
        def getSum(a,b):
            sm = 0
            for i in range(len(A)-a+1):
                s = S[i+a-1] - (S[i-1] if i > 0 else 0)
                for j in range(i+a,len(A)-b+1):
                    sm  = max(sm, s + S[j+b-1] - S[j-1])
            return sm
        return max(getSum(L,M),getSum(M,L))
            
            
            


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix = [0] * (len(A) + 1)
        for i in range(1, len(A) + 1):
            prefix[i] = prefix[i-1] + A[i-1]
        def get_subsum(i, j):
            return prefix[j+1] - prefix[i]
        # L before M
        result = 0
        for i in range(len(A) - L - M + 1):
            # maxi = len(A) - L - M
            # maxiend = len(A) - M - 1
            sub1 = get_subsum(i, i + L - 1)
            for j in range(i + L, len(A) - M + 1):
                # minj = L
                # maxj = len(A) - M
                # maxjend = len(A) - 1
                sub2 = get_subsum(j, j + M - 1)
                result = max(result, sub1 + sub2)
        # M before L
        for i in range(len(A) - L - M + 1):
            sub1 = get_subsum(i, i + M - 1)
            for j in range(i + M, len(A) - L + 1):
                sub2 = get_subsum(j, j + L - 1)
                result = max(result, sub1 + sub2)
        return result


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def getMax(p, N):
            _max = 0
            for i in range(len(p) - N):
                _max = max(p[i + N] - p[i], _max)
            return _max

        pre = [ 0 ]  * (len(A) + 1)
        for i in range(0, len(A)):
            pre[i + 1] = pre[i] + A[i]
        _max = 0
        for i in range(len(A) - max(L, M)):
            _max = max(getMax(pre[:i+L+1], L) + getMax(pre[i+L:], M), _max)
        for i in range(len(A) - max(L, M)):
            _max = max(getMax(pre[:i+M+1], M) + getMax(pre[i+M:], L), _max)
        return _max


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        tl = sum(A[:L])
        ll = [tl]
        for i in range(L,len(A)):
            tl-=A[i-L]
            tl+=A[i]
            ll.append(tl)
        print(ll)
        tl = sum(A[:M])
        ml = [tl]
        for i in range(M,len(A)):
            tl-=A[i-M]
            tl+=A[i]
            ml.append(tl)
        print(ml)
        maxx = 0
        for i in range(len(ll)):
            for j in range(len(ml)):
                if i+L-1<j or j+M-1<i:
                    maxx = max(maxx, ll[i]+ml[j])
        return maxx

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        tl = sum(A[:L])
        ll = [tl]
        for i in range(L,len(A)):
            tl-=A[i-L]
            tl+=A[i]
            ll.append(tl)
        # print(ll)
        tl = sum(A[:M])
        ml = [tl]
        for i in range(M,len(A)):
            tl-=A[i-M]
            tl+=A[i]
            ml.append(tl)
        # print(ml)
        maxx = 0
        for i in range(len(ll)):
            for j in range(len(ml)):
                if i+L-1<j or j+M-1<i:
                    maxx = max(maxx, ll[i]+ml[j])
        return maxx

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        start=0
        end=L
        t=sum(A[start:end])
        maxs=0
        while end<len(A)+1:
            pin1=0
            end1=M
            tot=sum(A[pin1:end1])
            while end1<start+1:
                #print(pin1,end1,t,tot,'yo')
                if t+tot>maxs:
                    maxs=t+tot
                tot=tot-A[pin1]
                tot=tot+A[end1]
                pin1+=1
                end1+=1
            pin2=end
            end2=end+M
            tot2=sum(A[pin2:end2])
            while end2<=len(A):
                #print(pin2,end2,t,tot2,'po')
                if t+tot2>maxs:
                    maxs=t+tot2
                if end2==len(A):
                    break
                tot2=tot2-A[pin2]
                tot2=tot2+A[end2]
                pin2+=1
                end2+=1
            if end==len(A):
                break
            t=t-A[start]
            t=t+A[end]
            start+=1
            end+=1
            #print(t,maxs)
        return maxs
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        NA = len(A)
        N1, N2 = max(L, M), min(L, M)
        sum_window = [[0]*NA for _ in range(2)]
        sum1 = sum2 = max_sum = 0
        for i, v in enumerate(A):
            if i >= N1:
                sum1 -= A[i-N1]
            if i >= N2:
                sum2 -= A[i-N2]
            sum1 += v
            sum2 += v
            sum_window[0][i] = sum1
            sum_window[1][i] = sum2
            
            if i >= N1:
                for j in range(i-N1+1):
                    max_sum = max(max_sum, sum_window[0][i]+sum_window[1][j])
                for j in range(i-N2+1):
                    max_sum = max(max_sum, sum_window[1][i]+sum_window[0][j])
                
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        
        arr = [A[0]]
        for i in range(1, n):
            arr.append(arr[-1] + A[i])
        arr = arr + [0]
        
        _max = 0
        for i in range(n - L + 1):
            for j in range(n - M + 1):
                if (i <= j <= i + L - 1) or (j <= i <= j + M - 1):
                    continue
                tmp = (arr[i + L - 1] - arr[i - 1]) + (arr[j + M - 1] - arr[j - 1])
                _max = max(_max, tmp)
        return _max

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        n = len(A)
        
        run_sum = [0] * (n+1)
        cur_sum = 0
        
        for i in range(1, n+1):
            cur_sum += A[i-1]
            run_sum[i] = cur_sum
        
        ans = 0
        for i in range(1, n - L + 2):
            L_sum = run_sum[i+L-1] - run_sum[i-1]
            for j in range(1, n - M + 2):
                if i+L-1 < j or j+M-1 < i:
                    M_sum = run_sum[j+M-1] - run_sum[j-1]
                    ans = max(ans, L_sum + M_sum)
        return ans
        
        


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        dpA = self.sumArray(A, L)
        dpB = self.sumArray(A, M)
        print(dpA)
        print(dpB)
        max_v = 0
        for i in range(len(dpA)):
            for m in range(len(dpB)):
                if m >= i and m - i < L:
                    continue
                if i >= m and i - m < M:
                    continue
                max_v = max(max_v, dpA[i] + dpB[m])
        return max_v
        
        
    def sumArray(self, lst, length):
        result = []
        for i in range(len(lst) - length + 1):
            sub_sum = lst[i]
            for m in range(1, length):
                sub_sum += lst[i + m]
            result.append(sub_sum)
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        space=len(A)-L-M
        maxx=0
        for i in range(1,space+2):
            a=0
            b=L-1
            c=b+i
            d=c+M-1
            leftSum=sum(A[a:b+1])
            rightSum=sum(A[c:d+1])
            while d<len(A):
                maxx=max(maxx,leftSum+rightSum)
                a+=1
                b+=1
                c+=1
                d+=1
                if d<len(A):
                    leftSum-=A[a-1]
                    leftSum+=A[b]
                    rightSum-=A[c-1]
                    rightSum+=A[d]
        maxx2=0
        for i in range(1,space+2):
            a=0
            b=M-1
            c=b+i
            d=c+L-1
            leftSum=sum(A[a:b+1])
            rightSum=sum(A[c:d+1])
            while d<len(A):
                maxx2=max(maxx2,leftSum+rightSum)
                a+=1
                b+=1
                c+=1
                d+=1
                if d<len(A):
                    leftSum-=A[a-1]
                    leftSum+=A[b]
                    rightSum-=A[c-1]
                    rightSum+=A[d]
            
        return max(maxx,maxx2)
                    
                
            
            



class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        dl = {}
        dm = {}
        
        if M > L:
            M,L = L,M
        
        ls = sum(A[0:L])
        ms = sum(A[0:M])
        
        dl[(0,L-1)] = ls
        dm[(0,M-1)] = ms
        
        c = 0
        while c + L < len(A):
            ls -= A[c]
            ls += A[L+c]
            
            #print(0+c,ls,L+c,A[c],A[L+c])
            
            dl[(0+c+1,L+c)] = ls
            c += 1
        
        c = 0
        while c + M < len(A):
            ms -= A[c]
            ms += A[M+c]
            dm[(0+c+1,M+c)] = ms
            c += 1
            
        dll = sorted(list(dl.items()),key=lambda x:x[1],reverse=True)
        mll = sorted(list(dm.items()),key=lambda x:x[1],reverse=True)
        
        #print(dll,mll)
        
        f = -1
        for x in dll:
            lower = x[0][0]
            upper = x[0][1]
            val = x[1]
            
            for y in mll:
                ly = y[0][0]
                uy = y[0][1]
                yval = y[1]
                
                
                
                if lower <= ly <= upper or lower <= uy <= upper:
                    continue
                maxVal = yval + val
                
                if maxVal == 125:
                    print(lower,upper,ly,uy)
                    print(x,y)
                
                f = max(maxVal,f)
                
        return f

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        max_two_sum = 0        
        N = len(A)
        def maxOverlap(arr: List[int]) -> int:
            n = len(arr)
            if n < L:
                return -1 
            roll_max = 0
            
            for i in range(L):
                roll_max += arr[i]
            curr_max = roll_max    
            
            start = 0
            for n in arr[L:]:
                roll_max = roll_max-arr[start] + n
                curr_max = max(curr_max, roll_max)
                start += 1
            return curr_max

        for x in range(N):
            curr_total = sum(A[x:x+M])
            first_half = maxOverlap(A[:x])
            second_half = maxOverlap(A[x+M:])
            max_two_sum = max(max_two_sum, curr_total + first_half, curr_total + second_half)
       
        return max_two_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        maxi = 0
        n = len(A)
        for i in range(1,n):
            A[i] += A[i-1]
        for i in range(n-L+1):
            for j in range(n-M+1):
                if (i>=j and i-j < M) or (i < j and j-i < L):
                    continue
                else:
                    istart = A[i-1] if i>0 else 0
                    jstart = A[j-1] if j>0 else 0
                    temp = A[i+L-1] - istart + A[j+M-1] - jstart
                    maxi = max(maxi,temp)
        return maxi
            


from functools import reduce

class Solution:
        
    
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        lsum = []
               
        csum = reduce(lambda a,b:a+b, A[:L]) 
        lsum.append(csum)
        
        for i in range(L, len(A)):
            csum += A[i] - A[i-L]
            lsum.append(csum)
            
        msum = []
        csum = reduce(lambda a,b:a+b, A[:M])
            
        msum.append(csum)
        
        for i in range(M, len(A)):
            csum += A[i] - A[i-M]
            msum.append(csum)
            
        maxSum = 0
        for i in range(len(A)-L+1):
            ls = i
            le = i + L - 1
            
            for j in range(len(A) - M+1):
                ms = j
                me = j + M - 1
                
                if (le < ms) or (me < ls):
                    maxSum = max(maxSum, lsum[ls] + msum[ms])
                    
        return maxSum    

class Solution:
    
    def maxSumTwoNoOverlap(self, A, L, M):
        for i in range(1, len(A)):
            A[i] += A[i - 1]
        res, Lmax, Mmax = A[L + M - 1], A[L - 1], A[M - 1]
        for i in range(L + M, len(A)):
            Lmax = max(Lmax, A[i - M] - A[i - L - M])
            Mmax = max(Mmax, A[i - L] - A[i - L - M])
            res = max(res, Lmax + A[i] - A[i - M], Mmax + A[i] - A[i - L])
        return res

import sys
class Solution:
    
    def is_overlap(self,i,j,L,M):
        if len(set(range(i,i+L)) & set(range(j,j+M))) > 0:
            return True
        else:
            return False
        
        
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        max_two_sum = 0        
        N = len(A)
        def maxOverlap(arr: List[int]) -> int:
            n = len(arr)
            if n < L:
                return -1 
            roll_max = 0
            
            for i in range(L):
                roll_max += arr[i]
            curr_max = roll_max    
            
            start = 0
            for n in arr[L:]:
                roll_max = roll_max-arr[start] + n
                curr_max = max(curr_max, roll_max)
                start += 1
            return curr_max

        for x in range(N):
            curr_total = sum(A[x:x+M])
            first_half = maxOverlap(A[:x])
            second_half = maxOverlap(A[x+M:])
            max_two_sum = max(max_two_sum, curr_total + first_half, curr_total + second_half)
       
        return max_two_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        max_found = 0
        sums = {}
        self.sumsOfL(A, L, sums)
        for i in range(len(A) - M + 1):
            available = self.getAvailableIndices(A, L, M, i)
            current_sum = sum(A[i:i+M])
            for j in available:
                max_found = max(max_found, sums[j] + current_sum)
        return max_found
        
    def getAvailableIndices(self, A, L, M, i):
        available = []
        for j in range(len(A) - L + 1):
            if j < i - L or j >= i + M:
                available.append(j)
        return available

    def sumsOfL(self, A, L, dictionary):
        left = 0
        right = L
        for i in range(len(A) - L + 1):
            dictionary[left] = sum(A[left:right])
            left += 1
            right += 1


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        m_res = [None for i in range(len(A)-M+1)]
        m = 0
        for i in range(len(A)-L+1):
            ts = sum(A[i:i+L])
            for j in range(len(A)-M+1):
                if j+M <= i or j >= i+L:
                    if m_res[j] is None:
                        m_res[j] = sum(A[j:j+M])
                    m = max(m, ts+m_res[j])
        return m

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        '''
        O(n^2)
        '''
        
            
        long = L if L > M else M
        short = M if M < L else L
        
        global_max = 0
        for i in range(0, len(A)-long+1):
            temp1 = sum(A[i:i+long])
            # subA = A[:i] + A[i+long:]
            # check left part
            left = A[:i]
            right = A[i+long:]
            if len(left) >= short:
            # check right part
                for j in range(0, len(left)-short+1):
                    temp2 = sum(left[j:j+short])
                    if temp1 + temp2 > global_max:
                        global_max = temp1 + temp2
            if len(right) >= short:
                for j in range(0, len(right)-short+1):
                    temp2 = sum(right[j:j+short])
                    if temp1 + temp2 > global_max:
                        global_max = temp1 + temp2
            
        return global_max

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        # Let's try a relatively naive solution first.
        # Compute the cumsums. Let cumsum(k) be the cumsum upto and incl. A[k]
        # Now, V(i,j) = cumsum(i+L-1) - cumsum(i-1) + cumsum(j+M-1) - cumsum(j-1)
        # With i and j satisfying the constraints.
        # Then we simply have to maximize this value over all possible values of i and j
        # subject to the constraint.
        
        n = len(A)
        # Corner cases
        if L + M == n:
            return sum(A)
        
        # We'll use array with cumsum[k] equivalent to cumsum(k-1) being the cumsum of the first
        # k elements (i.e. upto and including A[k-1]). A[0] = 0, being the cumsum of the first zero elements.
        cumsum = [0]*(n+1)
        for i in range(n):
            cumsum[i+1] = cumsum[i] + A[i]
            
        def good_combo(i, j):
            # Return True <=> L-length subarray at i intersects with M-length subarry starting at j
            return i+L-1 < j or j+M-1 < i
            
        res = -float('inf')
        for i in range(n-L+1):
            for j in range(n-M+1):
                if good_combo(i, j):
                    res = max(res, cumsum[i+L] - cumsum[i] + cumsum[j+M] - cumsum[j])
        return res
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        maxi = 0
        n = len(A)
        dp = {}
        dp[(0,L)] = sum(A[0:L])+sum(A[L:L+M])
        dp[(M,0)] = sum(A[0:M])+sum(A[M:L+M])
        for i in range(n-L+1):
            for j in range(n-M+1):
                if (i>=j and i-j < M) or (i < j and j-i < L):
                    continue
                else:
                    if (i,j-1) in dp:
                        dp[(i,j)] = dp[(i,j-1)] - A[j-1] + A[j+M-1]
                    elif (i-1,j) in dp:
                        dp[(i,j)] = dp[(i-1,j)] - A[i-1] + A[i+L-1]
                    maxi = max(maxi,dp[(i,j)])
        return maxi
            


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        acc=[0]+[*itertools.accumulate(A)]
        def getmaxfrom(i, x):
            return max(acc[j+x]-acc[j] for j in range(i,len(acc)-x))
            # s = 0
            # res = 0
            # for j in range(i, len(A)):
            #     s+=A[j]
            #     if j-i==x:
            #         s-=A[i]
            #         i+=1
            #     res = max(res, s)
            # return res
        
        ans = 0
        s = 0
        i = 0
        for j in range(len(A)-M):
            s+=A[j]
            if j-i == L:
                s-=A[i]
                i+=1
            ans = max(ans, s + getmaxfrom(j+1, M))
        
        s = 0
        i = 0
        for j in range(len(A)-L):
            s+=A[j]
            if j-i == M:
                s-=A[i]
                i+=1
            ans = max(ans, s + getmaxfrom(j+1, L))
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        l=len(A)
        if L<M:
            M,L=L,M
        # L 大
        ans=0
        for i in range(l-L+1):
            tmp=sum(A[i:i+L])
            j=0
            while j<(l-M+1):
                if i<j+M<i+L:
                    j=i+L
                else:
                    ans=max(ans,tmp+sum(A[j:j+M]))
                    j+=1
                    
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if L + M > len(A):
            assert False
        
        l = []
        s = 0
        for i in range(len(A) - L + 1):
            if i == 0:
                s = sum(A[:L])
            else:
                s -= A[i - 1]
                s += A[i + L - 1]
            l.append((-s, (i, i + L - 1)))
        l = sorted(l, key=lambda tup : tup[0])
        #print(l)
        m = []
        s = 0
        for i in range(len(A) - M + 1):
            if i == 0:
                s = sum(A[:M])
            else:
                s -= A[i - 1]
                s += A[i + M - 1]
            m.append((-s, (i, i + M - 1)))
        m = sorted(m, key=lambda tup : tup[0])
        
        maximum = 0
        for i in range(len(l)):
            for j in range(len(m)):
                sl, (il, jl) = l[i]
                sm, (im, jm) = m[j]
                sl, sm = -sl, -sm
                if sl + sm > maximum:
                    if jl < im or jm < il:
                        maximum = sl + sm
                else:
                    break
        
        return maximum
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        LList, MList = [], []
        thisSum = sum(A[:L])
        LList.append((thisSum, 0))
        for idx in range(L, len(A)):
            thisSum += A[idx] - A[idx - L]
            LList.append((thisSum, idx - L + 1))
        thisSum = sum(A[:M])
        MList.append((thisSum, 0))
        for idx in range(M, len(A)):
            thisSum += A[idx] - A[idx - M]
            MList.append((thisSum, idx - M + 1))
        # LList.sort(reverse=True)
        # MList.sort(reverse=True)
        allHeap = []
        for LEle in LList:
            for MEle in MList:
                heapq.heappush(allHeap, (- LEle[0] - MEle[0], LEle[1], MEle[1]))
        while allHeap:
            twoSum, lidx, midx = heapq.heappop(allHeap)
            if lidx + L - 1 < midx or midx + M - 1 < lidx:
                return -twoSum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def slidingWindow(windowLength):
            windowMap = {}
            currSum = sum(A[:windowLength])
            windowMap[(0, windowLength - 1)] = currSum
            
            for i in range(windowLength, len(A)):
                currSum -= A[i - windowLength]
                currSum += A[i]
                windowMap[(i - windowLength + 1, i)] = currSum
                
            return windowMap
                
        
        firstWindowMap = slidingWindow(L)
        secondWindowMap = slidingWindow(M)
        
        first = []
        second = []
        
        for x in firstWindowMap:
            first.append([firstWindowMap[x], x])
            
        for x in secondWindowMap:
            second.append([secondWindowMap[x], x])
        
        most = 0
        
        for i in range(len(first)):
            for j in range(len(second)):
                val1 = first[i][0]
                val2 = second[j][0]
                range1 = first[i][1]
                range2 = second[j][1]
                r1x = range1[0]
                r1y = range1[1]
                r2x = range2[0]
                r2y = range2[1]
                if not ((r2x <= r1x <= r2y) or (r1x <= r2x <= r1y)):
                    most = max(most, val1 + val2)
                    
        return most

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        acc=[0]+[*itertools.accumulate(A)]
        def getmaxfrom(i, x):
            return max(acc[j+x]-acc[j] for j in range(i,len(acc)-x))
        
        ans = 0
        s = 0
        i = 0
        for j in range(len(A)-M):
            s+=A[j]
            if j-i == L:
                s-=A[i]
                i+=1
            ans = max(ans, s + getmaxfrom(j+1, M))
        
        s = 0
        i = 0
        for j in range(len(A)-L):
            s+=A[j]
            if j-i == M:
                s-=A[i]
                i+=1
            ans = max(ans, s + getmaxfrom(j+1, L))
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        length = len(A)
        if length < L + M:
            return 0
        if length == L + M:
            return sum(A)
        res = 0
        for i in range(length - L + 1):
            s1 = sum(A[i:i+L])
            if i >= M:
                for j in range(i-M+1):
                    s2 = sum(A[j:j+M])
                    if res < s1 + s2:
                        res = s1 + s2
                for j in range(i + L, length - M + 1):
                    s2 = sum(A[j:j+M])
                    if res < s1 + s2:
                        res = s1 + s2
            else:
                for j in range(i + L, length - M + 1):
                    s2 = sum(A[j:j+M])
                    if res < s1 + s2:
                        res = s1 + s2
        return res


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if not A:
            return 0
        
        n = len(A)
      

        m_sum = 0
        for i in range(n-L+1):
            i_sum = sum(A[i:i+L])
            for j in range(i+L, n-M+1):
                m_sum = max(m_sum, (i_sum + sum(A[j:j+M])))
            for j in range(i-M+1):
                m_sum = max(m_sum, (i_sum + sum(A[j:j+M])))
        
        return m_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        out = 0
        for i in range(n-L + 1):
            l = sum(A[i:i+L])
            m = [sum(A[j:j+M]) for j in range(i + L, n-M+1)
                 ] + [sum(A[j:j+M]) for j in range(i-M)]
            if l and m:
                out = max(out, l + max(m))

        return out

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        max_sum = 0
        
        @lru_cache
        def _calculateSumFromIndex(i, length):
            return sum(A[i:i+length])
        
        for l in range(len(A)-L+1):
            l_sum = _calculateSumFromIndex(l, L)
            if l >= M:
                for m in range(0, l-M+1):
                    m_sum = _calculateSumFromIndex(m, M)
                    max_sum = max(max_sum, l_sum+m_sum)
            if len(A) - l+1 >= M:
                for m in range(l+L, len(A)-M+1):
                    m_sum = _calculateSumFromIndex(m, M)
                    max_sum = max(max_sum, l_sum+m_sum)
        return max_sum
        
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def findMaxSum(A: List[int], L: int, M: int) -> int:
            max_num = 0
            for i in range(len(A)-L):
                L_slice = A[i:L+i]
                L_sum = sum(L_slice)
                for j in range(L+i,len(A)-M+1):
                    M_slice = A[j:M+j]
                    M_sum = sum(M_slice)
                    max_num = max(L_sum + M_sum, max_num)
            return max_num
        
        forwards_sum = findMaxSum(A,L,M)
        A.reverse()
        backwards_sum = findMaxSum(A,L,M)
        return max(forwards_sum,backwards_sum)


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        N = len(A)
        
        res = 0
        for i in range(N - L + 1):
            l_sum = sum(A[i:i + L])
            for j in list(range(i-M+1)) + list(range(i+L, N-M+1)):
                res = max(res, l_sum + sum(A[j:j + M]))
        return res

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if not A:
            return 0
        
        ldp = [0 for i in range(len(A))]
        mdp = [0 for j in range(len(A))]
        
        sum_l = sum(A[len(A)-L:])
        for i in range(len(A)-L, -1, -1):
            sum_l = max(sum_l, sum(A[i:i+L]))
            ldp[i] = sum_l
                
        sum_m = sum(A[len(A)-M:])
        for i in range(len(A)-M, -1, -1):
            sum_m = max(sum_m, sum(A[i:i+M]))
            mdp[i] = sum_m
                
        print(ldp)
        print(mdp)
                
        ret = float('-inf')
        
        for i in range(len(A)-L-M+1):
            ret = max(ret, sum(A[i:i+L]) + mdp[i+L], sum(A[i:i+M]) + ldp[i+M])
        
        return ret

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def findMaxSum(A: List[int], L: int, M: int) -> int:
            max_num = 0
            for i in range(len(A)-L):
                L_slice = A[i:L+i]
                L_sum = sum(L_slice)
                for j in range(L+i,len(A)-M+1):
                    M_slice = A[j:M+j]
                    M_sum = sum(M_slice)
                    max_num = max(L_sum + M_sum, max_num)
            return max_num
        
        forwards_sum = findMaxSum(A,L,M)
        A.reverse()
        backwards_sum = findMaxSum(A,L,M)
        return max(forwards_sum,backwards_sum)

from typing import List


class Solution:

    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def findMaxSum(A, L, M):
            max_sum = 0

            for i in range(len(A) - L):
                L_slice = A[i: L + i]
                L_sum = sum(L_slice)

                for j in range(L + i, len(A) - M + 1):
                    M_slice = A[j: M + j]
                    M_sum = sum(M_slice)

                    max_sum = max(max_sum, L_sum + M_sum)
            return max_sum

        forward_sum = findMaxSum(A, L, M)
        A.reverse()
        backward_sum = findMaxSum(A, L, M)

        return max(forward_sum, backward_sum)



class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def findMaxSum(A,L,M):
            max_num = 0
            for i in range(len(A)-L):
                L_slice = A[i:L+i]
                L_sum = sum(L_slice)
                for j in range(L+i,len(A)-M+1):
                    M_slice = A[j:M+j]
                    M_sum = sum(M_slice)
                    max_num = max(L_sum + M_sum, max_num)
            return max_num
        forwards_sum = findMaxSum(A,L,M)
        A.reverse()
        backwards_sum = findMaxSum(A,L,M)
        return max(forwards_sum,backwards_sum)

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def findMaxSum(A: List[int], L: int, M: int) -> int:
            max_num = 0
            for i in range(len(A)-L):
                L_slice = A[i:L+i]
                L_sum = sum(L_slice)
                for j in range(L+i,len(A)-M+1):
                    M_slice = A[j:M+j]
                    M_sum = sum(M_slice)
                    max_num = max(L_sum + M_sum, max_num)
            return max_num
        
        forwards_sum = findMaxSum(A,L,M)
        A.reverse()
        backwards_sum = findMaxSum(A,L,M)
        return max(forwards_sum,backwards_sum)


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def find_maxsum(arr,l,m):
            max_sum = 0
            for i in range(len(arr)-l):
                l_slice = arr[i:i+l]
                l_sum = sum(l_slice)
                for j in range(i+l,len(arr)-m+1):
                    m_slice = arr[j:j+m]
                    m_sum = sum(m_slice)
                    max_sum = max(max_sum, l_sum+m_sum)
            return max_sum
        def maximum_sum(arr, l, m):
            rev_arr = list(reversed(arr))
            return max(find_maxsum(arr,l,m), find_maxsum(rev_arr,l,m))
        return maximum_sum(A,L,M)

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def traversal(A, L, M):
            maxi = 0
            for i in range(len(A)-L):
                L_slice = A[i:L+i]
                L_sum = sum(L_slice)
                
                for j in range(L+i,len(A)-M+1):
                    M_slice = A[j:M+j]
                    M_sum = sum(M_slice)
                    
                    maxi = max(maxi, L_sum+M_sum)
            return maxi
        forwards_sum = traversal(A,L,M)
        A.reverse()
        backwards_sum = traversal(A,L,M)
        return max(forwards_sum,backwards_sum)


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        S = [0] * (len(A) + 1)
        for i in range(1, len(A)+1):
            S[i] += S[i-1] + A[i-1]
        
        lmax, rmax = 0, 0
        for j in range(L, len(S)-M):
            lmax = max(lmax, S[j] - S[j-L])
            rmax = max(rmax, S[j+M] - S[j] + lmax)
            
        
        lmax2, rmax2 = 0, 0
        for j in range(M, len(S)-L):
            lmax2 = max(lmax2, S[j] - S[j-M])
            rmax2 = max(rmax2, S[j+L] - S[j] + lmax2)
        
        return max(rmax, rmax2)

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
      
      l_subarray_sums = [sum(A[i:i + L]) for i in range(0, len(A) - L + 1)]
      m_subarray_sums = [sum(A[i:i + M]) for i in range(0, len(A) - M + 1)]
      
      max_sum = 0
      for i, l_subarray_sum in enumerate(l_subarray_sums):
        if not m_subarray_sums[i + L:]:
          continue
        
        
        max_complement = max(m_subarray_sums[i + L:])
        
        if l_subarray_sum + max_complement > max_sum:
          max_sum = l_subarray_sum + max_complement
          print(f'l sum : {l_subarray_sum} | m sum : {max_complement}')
        
      for i, m_subarray_sum in enumerate(m_subarray_sums):
        if not l_subarray_sums[i + M:]:
          continue
          
        max_complement = max(l_subarray_sums[i + M:])
        
        if m_subarray_sum + max_complement > max_sum:
          max_sum = m_subarray_sum + max_complement
          print(f'm sum : {m_subarray_sum} | m sum : {max_complement}')
        
      return max_sum

from functools import reduce
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        def leftRight(lst, l, m):
            presum = reduce(lambda cum, cur: cum + [cur + cum[-1]], lst, [0])
            res = float('-inf')
            curL = presum[l]
            mxL = float('-inf')
            
            for i in range(l+m-1, len(lst)):
                if i > l + m - 1:
                    curL = curL - lst[i - (l+m)] + lst[i-m]
                    
                mxL = max(mxL, curL)
                res = max(res, mxL + presum[i+1] - presum[i-m+1])
            
            return res
        
        return max(leftRight(A, L, M), leftRight(A[::-1], L, M))

    # better: fix the middle part, keep track of the max of the left and right part of the middle part.

    # def maxSumTwoNoOverlap(self, A, L, M):
    #     for i in xrange(1, len(A)):
    #         A[i] += A[i - 1]
    #     res, Lmax, Mmax = A[L + M - 1], A[L - 1], A[M - 1]
    #     for i in xrange(L + M, len(A)):
    #         Lmax = max(Lmax, A[i - M] - A[i - L - M])
    #         Mmax = max(Mmax, A[i - L] - A[i - L - M])
    #         res = max(res, Lmax + A[i] - A[i - M], Mmax + A[i] - A[i - L])
    #     return res
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        M_sum_greater_than = [0]*len(A)
        M_sum_smaller_than = [0]*len(A)
        
        prefix_sum = [A[0]]
        for n in A[1:]:
            prefix_sum.append(prefix_sum[-1]+n)
        
        for i in range(M-1, len(A)):
            if i < M: M_sum_smaller_than[i] = max(M_sum_smaller_than[i-1], prefix_sum[i])
            else: 
                M_sum_smaller_than[i] = max(M_sum_smaller_than[i-1], prefix_sum[i]-prefix_sum[i-M])
        
        for j in range(len(A)-M, -1, -1):
            if j == 0: M_sum_greater_than[j] = max(M_sum_greater_than[j+1], prefix_sum[j+M-1])
            else: M_sum_greater_than[j] = max(M_sum_greater_than[min(j+1, len(A)-1)], prefix_sum[j+M-1]-prefix_sum[j-1])
        
        max_sum = 0
        for start in range(len(A)-L+1):
            if start == 0: sum_L = prefix_sum[start+L-1]
            else: sum_L = prefix_sum[start+L-1] - prefix_sum[start-1]
            
            if start-1 >= M-1:
                max_sum = max(max_sum, sum_L + M_sum_smaller_than[start-1])
            if start+L <= len(A)-M:
                max_sum = max(max_sum, sum_L + M_sum_greater_than[start+L])
            
        return max_sum
        


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        i=0
        maxL = []
        maxM = []
        maxSum = 0
        
        while i<=len(A)-L:
            maxL.append(sum(A[i:i+L]))
            i+=1
            
        i = 0
        while i<=len(A)-M:
            maxM.append(sum(A[i:i+M]))
            i+=1

        for i,elem in enumerate(maxL):
            if i-M<=0:
                prefix = []
            else:
                prefix = maxM[0:i-M]
            
            if len(maxM[i+L:]+prefix)== 0:
                continue
            maxSum = max(maxSum,elem+max(prefix+maxM[i+L:]))
        
        return maxSum        

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix_sum = [0] * (len(A)+1)
        for i in range(len(A)): prefix_sum[i+1] = prefix_sum[i] + A[i]
        maxL = maxM = result = 0
        
        for i in range(M, len(prefix_sum) - L):
            # optimal when L-list start at i+1 and occur after M-list
            maxM = max(maxM, prefix_sum[i] - prefix_sum[i-M])
            result = max(result, maxM + prefix_sum[i+L] - prefix_sum[i])
        
        for i in range(L, len(prefix_sum) - M):
            # optimal when M-list start at i+1 and occur after L-list
            maxL = max(maxL, prefix_sum[i] - prefix_sum[i-L])
            result = max(result, maxL + prefix_sum[i+M] - prefix_sum[i])
        
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        L, M = min(L, M), max(L, M)
        
        lSums = [0] * len(A)
        mSums = [0] * len(A)
        
        lSums[L-1] = sum(A[:L])
        mSums[M-1] = sum(A[:M])
        
        for i in range(L, len(A)):
            lSums[i] = lSums[i-1] + A[i] - A[i-L]
        
        for i in range(M, len(A)):
            mSums[i] = mSums[i-1] + A[i] - A[i-M]
            
        print(lSums)
        print(mSums)
        
        greatest = 0
        for i in range(L-1, len(A)-M):
            greatest = max(greatest, max(lSums[:i+1]) + max(mSums[i+M:]))
        
        for i in range(M-1, len(A)-L):
            greatest = max(greatest, max(mSums[:i+1]) + max(lSums[i+L:]))
            
        return greatest

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if L + M > len(A):
            return 0
        max_end = [0 for i in range(len(A))]
        max_start = [0 for i in range(len(A))]
        
        def max_sum(L, M):
            sum1, sum2, max_sum1, max_sum2, max_sum = 0, 0, 0, 0, 0
            for i in range(len(A)):
                max_sum2 = max(sum2, max_sum2)
                max_start[len(A)-i-1] = max_sum2
                if i >= L:
                    sum1 -= A[i-L]
                if i >= M:
                    sum2 -= A[len(A)-i+M-1]
                sum1 += A[i]
                sum2 += A[len(A)-1-i]
                max_sum1 = max(sum1, max_sum1)
                max_end[i] = max_sum1
            for i in range(L-1, len(A)-M):
                max_sum = max(max_sum, max_end[i]+max_start[i])
            return max_sum
        
        return max(max_sum(L, M), max_sum(M, L))
                    


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        dp1,dp2 = [0]*n,[0]*n
        
        for i in range(n-L+1):
            if i==0: dp1[i] = sum(A[i:i+L])
            else: dp1[i] = dp1[i-1]+A[i+L-1]-A[i-1]
        
        maxy = 0
        for i in range(n-M+1):
            if i==0: dp2[i] = sum(A[i:i+M])
            else: dp2[i] = dp2[i-1]+A[i+M-1]-A[i-1]
                
            if i>=L: maxy = max(maxy,dp2[i]+max(dp1[:i-L+1]))
            if i+M<n: maxy = max(maxy,dp2[i]+max(dp1[i+M:]))
        
        return maxy
        
        # maxy = 0
        # for a,b,d1,d2 in [(L,M,dp1,dp2), (M,L,dp2,dp1)]:
        #     i,j = 0,n-b
        #     while i+a<j:
        #         maxy = max(maxy,d1[i]+d2[j])
        #         if d1[i+1]>d1[i]: i+=1
        #         else: j-=1
        # print(L,dp1)
        # print(M,dp2)
        # return maxy


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        dp = [[0, 0, 0] for _ in range(len(A))]
        L, M = min(L, M), max(L, M)
        l_sum, m_sum = 0, 0
        for idx in range(L + M):
            if idx <= L - 1:
                l_sum += A[idx]
                if idx == L - 1:
                    dp[idx][0] = l_sum
            else:
                l_sum += A[idx] - A[idx - L]
                dp[idx][0] = l_sum if dp[idx - 1][0] < l_sum else dp[idx - 1][0]
            if idx <= M - 1:
                m_sum += A[idx]
                if idx == M - 1:
                    dp[idx][1] = m_sum
            else:
                m_sum += A[idx] - A[idx - M]
                dp[idx][1] = m_sum if dp[idx - 1][1] < m_sum else dp[idx - 1][1]              
        dp[L + M - 1][2] = max(l_sum + dp[idx - L][1], m_sum + dp[idx - M][0])
        for idx in range(L + M, len(A)):
            l_sum += A[idx] - A[idx - L]
            dp[idx][0] = l_sum if dp[idx - 1][0] < l_sum else dp[idx - 1][0]
            m_sum += A[idx] - A[idx - M]
            dp[idx][1] = m_sum if dp[idx - 1][1] < m_sum else dp[idx - 1][1]
            print((idx, l_sum, m_sum, dp[idx - L], dp[idx - M]))
            dp[idx][2] = max(dp[idx - 1][2], l_sum + dp[idx - L][1], m_sum + dp[idx - M][0])
        print(dp)
        return dp[len(A) - 1][2]


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        seg_sum_l = []
        seg_sum_m = []
        cum_sum = [0]
        n = len(A)
        for i, a in enumerate(A):
            cum_sum.append(a + cum_sum[-1])
            if i >= L-1:
                seg_sum_l.append(cum_sum[i+1] - cum_sum[i-L+1])
            else:
                seg_sum_l.append(-1)
            if i >= M-1:
                seg_sum_m.append(cum_sum[i+1] - cum_sum[i-M+1])
            else:
                seg_sum_m.append(-1)
        
        max_sum = -1
        for i in range(L-1, n):
            for j in range(M-1, i-L):
                cur_sum = seg_sum_l[i] + seg_sum_m[j]
                if cur_sum > max_sum:
                    max_sum = cur_sum
            for j in range(i+M, n):
                cur_sum = seg_sum_l[i] + seg_sum_m[j]
                if cur_sum > max_sum:
                    max_sum = cur_sum
        
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        largestSum = 0
        LList, MList = [0] * len(A), [0] * len(A)
        thisSum = sum(A[:L])
        LList[0] = thisSum
        for idx in range(len(A) - L):
            thisSum += A[idx + L] - A[idx]
            LList[idx + 1] = thisSum
        thisSum = sum(A[:M])
        MList[0] = thisSum
        for idx in range(len(A) - M):
            thisSum += A[idx + M] - A[idx]
            MList[idx + 1] = thisSum
        for idx in range(len(A) - M + 1):
            largestSum = max(largestSum, MList[idx] + max([0] + LList[:max(0, idx - L + 1)] + LList[idx + M:]))
        return largestSum

from functools import reduce
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        def leftRight(lst, l, m):
            presum = reduce(lambda cum, cur: cum + [cur + cum[-1]], lst, [0])
            res = float('-inf')
            curL = presum[l]
            mxL = float('-inf')
            
            for i in range(l+m-1, len(lst)):
                if i > l + m - 1:
                    curL = curL - lst[i - (l+m)] + lst[i-m]
                    
                mxL = max(mxL, curL)
                res = max(res, mxL + presum[i+1] - presum[i-m+1])
            
            return res
        
        return max(leftRight(A, L, M), leftRight(A[::-1], L, M))
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        Lsum = [(sum(A[:L]), 0)]
        Msum = [(sum(A[:M]), 0)]
        for i in range(1, len(A) - L + 1):
            Lsum.append((Lsum[-1][0] - A[i-1] + A[i+L-1], i))
        for i in range(1, len(A) - M + 1):
            Msum.append((Msum[-1][0] - A[i-1] + A[i+M-1], i))
        Lsum.sort(reverse=True)
        Msum.sort(reverse=True)
        ret = sum(A[:L+M])
        for li in range(len(Lsum)):
            breakFlag = True
            for mi in range(len(Msum)):
                if (Lsum[li][1] <= Msum[mi][1] and Lsum[li][1] + L > Msum[mi][1]) or (Msum[mi][1] <= Lsum[li][1] and Msum[mi][1] + M > Lsum[li][1]):
                    breakFlag = False
                    continue
                ret = max(ret, Lsum[li][0] + Msum[mi][0])
                break
            if breakFlag:
                break
        return ret


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        for i in range(1, len(A)):
            A[i] += A[i - 1]
        res, Lmax, Mmax = A[L + M - 1], A[L - 1], A[M - 1]
        for i in range(L + M, len(A)):
            Lmax = max(Lmax, A[i - M] - A[i - L - M])
            Mmax = max(Mmax, A[i - L] - A[i - L - M])
            res = max(res, Lmax + A[i] - A[i - M], Mmax + A[i] - A[i - L])
        return res

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        dp = [[0,0] for _ in range(n)]
        
        for i in range(L-1,n): # scan from left to right, get all dp[i][0] first
            if i>0: 
                dp[i][0] = max(dp[i-1][0], sum(A[i-L+1:i+1:+1]))
            else: dp[i][0] = A[0]
            
        for i in range(n-L,-1,-1): # scan from left to right, get all dp[i][0] first
            if i<n-1: 
                dp[i][1] = max(dp[i+1][1], sum(A[i:i+L:+1]))

            else: dp[i][1] = A[n-1]
        #print(dp)
        maximum = float('-inf')
        # Then for subarray M
        for i in range(0,n-M+1):
            s = sum(A[i:i+M:1])
            left = dp[i-1][0] if i-1>0 else 0
            right = dp[i+M][1] if i+M<n else 0
            #print(i,s, left, right)
            maximum = max(maximum, s+left, s+right)
        return maximum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        import heapq
        n = len(A)
        def get_subsum(L):
            Lsum = [sum(A[:L])]
            for i in range(1, n-L+1):
                Lsum.append(Lsum[i-1] + A[i+L-1] - A[i-1])
            return [(s, i) for i, s in enumerate(Lsum)]
        Lsum = get_subsum(L)
        # print(Lsum)
        Lsum.sort(reverse=True)
        Msum = get_subsum(M)
        # print(Msum)
        Msum.sort(reverse=True)
        def overlap(i, j, L=L, M=M):
            #i, i+L-1
            #j, j+M-1
            return j <= i < j+M or i <= j < i + L
        i = j = 0
        Llen = len(Lsum)
        Mlen = len(Msum)
        visited = set()
        stack = []
        heapq.heappush(stack, (0, (0,0)))
        while stack:
            _, (i, j) = heapq.heappop(stack)
            # visited.add((i,j))
            # print(i, j, Lsum[i], Msum[j])
            if not overlap(Lsum[i][1], Msum[j][1]):
                return Lsum[i][0] + Msum[j][0]
            if i < Llen - 1 and not (i+1, j) in visited:
                visited.add((i+1,j))
                heapq.heappush(stack, (-(Lsum[i+1][0] + Msum[j][0]), (i+1, j)))
            if j < Mlen - 1 and not (i,j+1) in visited:
                visited.add((i,j+1))
                heapq.heappush(stack, (-(Lsum[i][0] + Msum[j+1][0]), (i, j+1)))


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        result = 0
        lsum = sum(A[0:L])
        msum = sum(A[L:L+M])
        psum = 0
        j = 0
        result = max(result, max(lsum + msum, lsum + psum))
        # print(lsum, msum, psum, result)
        prefix = [0]*len(A)
        for i in range(0, len(A) - M + 1):
            prefix[i+M-1] = sum(A[i:i+M])
        # For the first run the below is imp
        for k in range(L+M-1, len(A)):
            result = max(result, lsum + prefix[k])
        for i in range(L, len(A)):
            lsum = lsum - A[i-L] + A[i]
            if i+M <= len(A) - 1:
                for k in range(i+M, len(A)):
                    result = max(result, lsum + prefix[k])
            if i-L > M-1:
                # print(i)
                for k in range(M-1, i-L):
                    result = max(result, lsum + prefix[k])
            # print(lsum, result)
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        Len = len(A) + 1
        prefix = [0] + A
        maxSum = 0
        for i in range(1, Len):
            prefix[i] = prefix[i - 1] + A[i - 1]
        i = L
        while i < Len:
            LSum = prefix[i] - prefix[i - L]
            j = M
            while j < i - L:
                MSum = prefix[j] - prefix[j - M]
                temp = LSum + MSum
                if temp > maxSum:
                    maxSum = LSum + MSum
                j += 1
            j = i + M
            while j < Len:
                MSum = prefix[j] - prefix[j - M]
                temp = LSum + MSum
                if temp > maxSum:
                    maxSum = temp
                j += 1
            i += 1
        return maxSum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        pref = [0] * (len(A)+1)
        for i in range(1, len(A)+1):
            pref[i] = pref[i-1] + A[i-1]
        l = [0] * (len(A)-L+1)
        m = [0] * (len(A)-M+1)
        for i in range(len(A)-L+1):
            l[i] = pref[i+L] - pref[i]
        for i in range(len(A)-M+1):
            m[i] = pref[i+M] - pref[i]
        ans = 0
        for i in range(len(l)):
            for j in range(i-M+1):
                ans = max(ans, l[i]+m[j])
            for j in range(i+L, len(A)-M+1):
                ans = max(ans, l[i]+m[j])
        return ans


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        res = 0
        psum = [0] * (n + 1)
        for i in range(n):
            psum[i+1] = psum[i] + A[i]
        for i in range(0, n - L + 1):
            ls = psum[i+L] - psum[i]
            lm = max(self._max_m(0, i, M, psum), self._max_m(i+L, n, M, psum))
            res = max(res, ls + lm)
        return res
    
    def _max_m(self, s, e, M, psum):
        res = 0
        for i in range(s, e - M + 1):
            res = max(res, psum[i+M] - psum[i])
        return res

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        tmp_sum = sum(A[:L])
        i = L
        L_sum = [tmp_sum]
        while i<len(A):
            tmp_sum -= A[i-L]
            tmp_sum += A[i]
            L_sum.append(tmp_sum)
            i += 1
            
        tmp_sum = sum(A[:M])
        i = M
        M_sum = [tmp_sum]
        while i<len(A):
            tmp_sum -= A[i-M]
            tmp_sum += A[i]
            M_sum.append(tmp_sum)
            i += 1
            
        max_sum = 0
        # L before M
        for i, lsum in enumerate(L_sum):
            for j in range(i+L, len(M_sum)):
                max_sum = max(max_sum, lsum+M_sum[j])
                
        # M before L
        for i, msum in enumerate(M_sum):
            for j in range(i+M, len(L_sum)):
                max_sum = max(max_sum, msum+L_sum[j])
                
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        dp = [[-1, -1] for i in range(len(A))]
        # print(dp)
        
        l = L-1
        dp[l][0] = sum(A[0:L])
        l += 1
        while l < len(A):
            dp[l][0] = dp[l-1][0] - A[l-L] + A[l]
            l += 1
        
        m = M-1
        dp[m][1] = sum(A[0:M])
        m += 1
        while m < len(A):
            dp[m][1] = dp[m-1][1] - A[m-M] + A[m]
            m += 1
        
        # dp.sort(reverse=True, key=lambda x: x[0])
        maxSum = -math.inf
        
        for i, sums in enumerate(dp):
            if sums[0] == -1:
                continue
            eligible_M = dp[:i-L+1] + dp[i+M:]
            # print (sums[0], eligible_M, max(eligible_M, key=lambda x: x[1])[1])
            maxSum = max(maxSum, sums[0] + max(eligible_M, key=lambda x: x[1])[1])
        
        # print(maxSum)
        # print(dp)
        return maxSum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        '''
            2:35
            # prefix sum  O(n)
            # for each L subarray:  O(n)
                check all M subarrays in its left or right, O(n)
                
            # O(n^2)
        '''
        
        N = len(A)
        
        prefix = [0] * (N+1)  # prefix[i]:  sum(A[0:i]) 
        for i in range(1,N+1):
            prefix[i] = prefix[i-1] + A[i-1]
        
        res = 0
        for Li in range(N-L+1): # 0..N-L
            Lj = Li + L # L..N
            sumL = prefix[Lj] - prefix[Li]
            sumM = 0 
            for Mi in range(Lj, N-M+1): # Lj..N-M
                Mj = Mi + M  # Lj+M..N
                sumM = max(sumM, prefix[Mj] - prefix[Mi])
            for Mi in range(0, Li-M+1):
                Mj = Mi + M
                sumM = max(sumM, prefix[Mj] - prefix[Mi])
            res = max(res, sumL+sumM)
        return res
            


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        resL = []
        resM = []

        for i in range(len(A) - L + 1):
            resL.append(sum(A[i:i + L]))
        for i in range(len(A) - M + 1):
            resM.append(sum(A[i:i + M]))
        print(resL)
        print(resM)
        i = 0
        maxValue = -1
        while i < len(resL):
            # right
            for j in range(i + L, len(resM)):
                maxValue = max(resL[i] + resM[j], maxValue)
            for j in range(min(i - M, len(resM))):
                maxValue = max(resL[i] + resM[j], maxValue)
            i += 1
        return maxValue

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if not A:
            return 0
        cumulatedSum = [0] * (len(A) + 1)
        result = 0
        for i in range(len(A)):
            cumulatedSum[i + 1] = cumulatedSum[i] + A[i]
        # L before M
        for i in range(len(A) - L + 1):
            # sum[i: i + L - 1]
            lSum = cumulatedSum[i + L] - cumulatedSum[i]
            for j in range(i + L, len(A) - M + 1):
                # sum[j, j + M -1]
                mSum = cumulatedSum[j + M] - cumulatedSum[j]
                result = max(result, lSum + mSum)
            
        for i in range(len(A) - M + 1):
            mSum = cumulatedSum[i + M] - cumulatedSum[i]
            for j in range(i + M, len(A) - L + 1):
                lSum = cumulatedSum[j + L] - cumulatedSum[j]
                result = max(result, lSum + mSum)
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefixSum = [0]  * (len(A)+1)
        for i in range(1, len(A)+1):
            prefixSum[i] = prefixSum[i-1] + A[i-1]
            
        # print(prefixSum)
        # print(M, L)
        ans = 0
        for i in range(M-1, len(A)):
            # print('i', i, i-(M-1))
            sumM = prefixSum[i+1] - prefixSum[i+1-M]
            sumL = 0
            for j in range(L-1, i-(M-1)):
                sumL = max(sumL, prefixSum[j+1] - prefixSum[j+1-L])
            # print('sumleft', sumL, L-1, i-(M-1))
            for j in range(i+1+L-1, len(A)):
                sumL = max(sumL, prefixSum[j+1] - prefixSum[j+1-L])
            # print('sumright', sumL)
            # print('sumM', sumM)
            ans = max(ans, sumM + sumL)
        return ans


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        cumsum = []
        N = len(A)
        
        for i in range(N):
            if i == 0:
                cumsum.append(A[i])
            else:
                cumsum.append(cumsum[i-1]+ A[i])
            
        l_sums = []
        i = 0
        while(i+L <= N):
            l_sums.append(cumsum[i+L-1]-cumsum[i] + A[i])
            i += 1
            
        m_sums = []
        i = 0
        while(i+M <= N):
            m_sums.append(cumsum[i+M-1]-cumsum[i] + A[i])
            i += 1
            
#         print(cumsum)
#         print(l_sums)
#         print(m_sums)
        
        i = 0
        j = len(m_sums)-1
        
        ans = 0
        
        for i in range(len(l_sums)):
            for j in range(i+L,len(m_sums)):
                curr_sum = l_sums[i] + m_sums[j]
                ans = max(ans,curr_sum)
                
        for i in range(len(m_sums)):
            for j in range(i+M,len(l_sums)):
                curr_sum = m_sums[i] + l_sums[j]
                ans = max(ans,curr_sum)
        
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        prefix = [0] * (n + 1)
        res = 0
        for i in range(0, n):
            prefix[i + 1] = prefix[i] + A[i]
        for i in range(0, n - L + 1):
            l_sum = prefix[i + L] - prefix[i]
            j, m_sum = i, 0
            while j - M >= 0:
                m_sum = max(m_sum, prefix[j] - prefix[j - M])
                j -= 1
            j = i + L
            while j + M <= n:
                m_sum = max(m_sum, prefix[j + M] - prefix[j])
                j += 1
            res = max(res, l_sum + m_sum)
        return res

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n, cur_sum, max_sum = len(A), 0, 0
        max_l = [[0,0] for _ in range(n+2)]
        
        for i in range(n):
            cur_sum += A[i]
            if i >= L - 1:
                max_l[i+1][0] = max(max_l[i][0], cur_sum)
                cur_sum -= A[i-L+1]
        
        cur_sum = 0
        for i in range(n-1, -1, -1):
            cur_sum += A[i]
            if i <= n - L:
                max_l[i+1][1] = max(max_l[i+2][1], cur_sum)
                cur_sum -= A[i+L-1]
        
        cur_sum = 0
        for i in range(n):
            cur_sum += A[i]
            if i >= M - 1:
                max_sum = max(max_sum, cur_sum + max_l[i-M+1][0], cur_sum + max_l[i+2][1])
                cur_sum -= A[i-M+1]
        
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefixSum = [0]  * (len(A)+1)
        for i in range(1, len(A)+1):
            prefixSum[i] = prefixSum[i-1] + A[i-1]
            
        ans = 0
        for i in range(M-1, len(A)):
            sumM = prefixSum[i+1] - prefixSum[i+1-M]
            sumL = 0
            for j in range(L-1, i-(M-1)):
                sumL = max(sumL, prefixSum[j+1] - prefixSum[j+1-L])
            for j in range(i+1+L-1, len(A)):
                sumL = max(sumL, prefixSum[j+1] - prefixSum[j+1-L])
            ans = max(ans, sumM + sumL)
        return ans


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        # i think u have to do smaller numbers first because the smaller set is contained within the larger set
        # returns indices
        
        # Greedy does not work; need to do this in n^2 time i think
#         def solve(size, a):
#             i= 0
#             j = i + size
#             m = [i,j] #max indices
#             s = sum(a[i:j]) # current sum
#             max_sum = s # max sum
#             while(j != len(a)):
#                 i+=1
#                 j+=1
#                 s -= a[i-1]
#                 s += a[j-1]
#                 if s > max_sum:
#                     max_sum = s
#                     m[0] = i
#                     m[1] = j
#             return m, max_sum
        
#         m, ms = solve(min(L,M), A)
#         # print(m, ms)
#         # A = A[:m[0]] + A[m[1]:]
#         # print(A)
#         m2, ms2 = solve(max(L,M), A[:m[0]] + A[m[1]:])
#         print(m, ms, m2, ms2)
        
#         m3, ms3 = solve(max(L,M), A)
#         m4, ms4 = solve(min(L,M), A[:m3[0]] + A[m3[1]:])
#         print(m3, ms3, m4, ms4)
#         return max(ms + ms2, ms3 + ms4)

        # On^2 time too slow
        # def solve(size1, size2, a):
        #     # current max
        #     curr = sum(a[0:0+size1]) + sum(a[size1: size1+size2])
        #     for i in range(len(a)-size2-size1+1):
        #         for j in range(i+size1, len(a)):
        #             temp = sum(a[i:i+size1]) + sum(a[j: j+size2]) # make this faster
        #             # temp = curr - a[j-1] + a[j+size2]
        #             # print(temp, i, i + size1, j, j + size2)
        #             if temp> curr:
        #                 curr = temp
        #     return curr
        # m = solve(L, M, A)
        # m2 = solve(M, L, A)
        # return max(m, m2)
        A = [0] + A
        for i in range(1,len(A)):
            A[i] += A[i-1] 
        # print(A[1]-A[0])
        # print(len(A))
        def solve(l,m,a):
            curr = 0
            # for i in range(len(a)-l-m+1):
            for i in range(len(a) - l+1):
                for j in range(i+l,len(a)-m):
                    # print(i, i+l, j, j+m, a[i+l] - a[i], a[j+m] - a[j])
                    temp = a[i+l] - a[i] + a[j+m] - a[j]
                    if temp > curr:
                        curr = temp
            return curr
        
        m2 = solve(M, L, A)
        m = solve(L, M, A)
        # return m2
        # print(m, m2)
        return max(m, m2)
            
                    
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        N = len(A)
        
        # generate prefix sum array
        prefix = [0] * (N + 1)
        for i in range(1, N + 1):
            prefix[i] = prefix[i - 1] + A[i - 1]
            
        max_sum = 0
        for end_l in range(L, N + 1):
            start_l = end_l - L
            sum1 = prefix[end_l] - prefix[start_l]
            
            for end_m in range(M, start_l):
                sum2 = prefix[end_m] - prefix[end_m - M]
                max_sum = max(max_sum, sum1 + sum2)
            for start_m in range(end_l, N - M + 1):
                sum2 = prefix[start_m + M] - prefix[start_m]
                max_sum = max(max_sum, sum1 + sum2)
            
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        sum = [0 for i in range(len(A))]
        sum[0] = A[0]
        
        for i in range(1, len(A)):
            sum[i] = sum[i-1] + A[i]
            
        res = -math.inf
        # L before M
        for i in range(len(A) - L):
            r = -math.inf
            for j in range(i + L, len(A) - M + 1):
                r = max(r, sum[j + M - 1] - sum[j-1])
            r += sum[i + L - 1] - (sum[i-1] if i - 1 > -1 else 0)
            res = max(res, r)
        
        # M before L
        for i in range(len(A) - M):
            r = -math.inf
            for j in range(i + M, len(A) - L + 1):
                r = max(r, sum[j + L - 1] - sum[j-1])
            r += sum[i + M - 1] - (sum[i-1] if i - 1 > -1 else 0)
            res = max(res, r)
            
        return res

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        
        prefix = [0] * (n + 1)
        
        for i in range(n):
            prefix[i+1] = prefix[i] + A[i]
            
        maxi = float('-inf')
        
        for startL in range(n-L+1):
            endL = startL + L - 1
            sumL = prefix[endL+1] - prefix[startL]
            for startM in range(startL-M+1):
                endM = startM + M - 1
                sumM = prefix[endM+1] - prefix[startM]
                maxi = max(maxi, sumM + sumL)
            for startM in range(endL+1, n-M+1):
                endM = startM + M - 1
                sumM = prefix[endM+1] - prefix[startM]
                maxi = max(maxi, sumM + sumL)
                
                
        return maxi

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        
        
        
        cumSum = [0]*(len(A)+1)
        
        for i,a in enumerate(A):
            cumSum[i+1] = cumSum[i]+a
            
        
        max_sum = 0
        for i in range(len(A)-L+1):
            sum_sub1 = 0
            sum_sub1 = cumSum[i+L] - cumSum[i]
            if i >= M:
                for j in range(i-M+1):
                    sum_sub2 = 0
                    sum_sub2 = cumSum[j+M] - cumSum[j]
                    sum_sub2 = sum_sub1 + sum_sub2
                    max_sum = max(max_sum, sum_sub2)
            if i+L <= len(A)-M:
                for j in range(i+L, len(A)-M+1):
                    sum_sub2 = 0
                    sum_sub2 = cumSum[j+M] - cumSum[j]
                    sum_sub2 = sum_sub1 + sum_sub2
                    max_sum = max(max_sum, sum_sub2)
                    
        return max_sum
                        
        
        
        


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        
        prefix = [0] * (n + 1)
        
        for i in range(n):
            prefix[i+1] = prefix[i] + A[i]
            
        maxi = float('-inf')
        for startL in range(n-L+1):
            endL = startL + L - 1
            sumL = prefix[endL+1] - prefix[startL]
            
            for startM in range(startL+1-M):
                endM = startM + M - 1
                sumM = prefix[endM+1] - prefix[startM]
                maxi = max(maxi, sumL + sumM)
                
            for startM in range(endL+1, n-M+1):
                endM = startM + M - 1
                sumM = prefix[endM+1] - prefix[startM]
                maxi = max(maxi, sumL + sumM)
                
        
        return maxi

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        
        sumL = sum(A[:L])
        sumM = sum(A[L:(L+M)])
        res = sumL + sumM
        for j in range(L+M, len(A)):
            sumM += A[j]-A[j-M]
            res = max(res, sumL+sumM)
        
        for i in range(L, len(A)):
            sumL += A[i]-A[i-L]
            if i-L+1 >= M:
                sumM = sum(A[:M])
                res = max(res, sumL+sumM)
                for j in range(M, i-L+1):
                    sumM += A[j]-A[j-M]
                    res = max(res, sumL+sumM)
            if i <= len(A)-M-1:
                sumM = sum(A[(i+1):(i+1+M)])
                for j in range(i+1+M, len(A)):
                    sumM += A[j]-A[j-M]
                    res = max(res, sumL+sumM)
        return res


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        result = 0
        lsum = sum(A[0:L])
        msum = sum(A[L:L+M])
        psum = 0
        j = 0
        result = max(result, max(lsum + msum, lsum + psum))
        # print(lsum, msum, psum, result)
        prefix = [0]*len(A)
        for i in range(0, len(A) - M + 1):
            prefix[i+M-1] = sum(A[i:i+M])
        for k in range(L+M-1, len(A)):
            result = max(result, lsum + prefix[k])
        for i in range(L, len(A)):
            lsum = lsum - A[i-L] + A[i]
            if i+M <= len(A) - 1:
                for k in range(i+M, len(A)):
                    result = max(result, lsum + prefix[k])
            if i-L > M-1:
                # print(i)
                for k in range(0, i-L):
                    result = max(result, lsum + prefix[k])
            # print(lsum, result)
        return result


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        result = 0
        lsum = sum(A[0:L])
        msum = sum(A[L:L+M])
        psum = 0
        j = 0
        result = max(result, max(lsum + msum, lsum + psum))
        # print(lsum, msum, psum, result)
        prefix = [0]*len(A)
        for i in range(0, len(A) - M + 1):
            prefix[i+M-1] = sum(A[i:i+M])
        for k in range(L+M-1, len(A)):
            result = max(result, lsum + prefix[k])
        for i in range(L, len(A)):
            lsum = lsum - A[i-L] + A[i]
            if i+M <= len(A) - 1:
                for k in range(i+M, len(A)):
                    result = max(result, lsum + prefix[k])
            if i-L > M-1:
                # print(i)
                for k in range(0, i-L):
                    result = max(result, lsum + prefix[k])
            # print(lsum, result)
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        result = 0
        lsum = sum(A[0:L])
        msum = sum(A[L:L+M])
        psum = 0
        j = 0
        result = max(result, max(lsum + msum, lsum + psum))
        # print(lsum, msum, psum, result)
        prefix = [0]*len(A)
        for i in range(0, len(A) - M + 1):
            prefix[i+M-1] = sum(A[i:i+M])
        # For the first run the below is imp
        for k in range(L+M-1, len(A)):
            result = max(result, lsum + prefix[k])
        for i in range(L, len(A)):
            lsum = lsum - A[i-L] + A[i]
            if i+M <= len(A) - 1:
                for k in range(i+M, len(A)):
                    result = max(result, lsum + prefix[k])
            if i-L > M-1:
                # print(i)
                for k in range(0, i-L):
                    result = max(result, lsum + prefix[k])
            # print(lsum, result)
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix_sum = [0] * (len(A)+1)

        for i in range(1, len(prefix_sum)):
            prefix_sum[i] = A[i-1] + prefix_sum[i-1]

        max_sum = 0

        # start with L
        for i in range(L, len(prefix_sum)):
            L_sum = prefix_sum[i] - prefix_sum[i-L]

            for j in range(i+M, len(prefix_sum)):
                M_sum = prefix_sum[j] - prefix_sum[j-M]
                max_sum = max(max_sum, L_sum + M_sum)

        # start with M
        for i in range(M, len(prefix_sum)):
            M_sum = prefix_sum[i] - prefix_sum[i-M]

            for j in range(i+L, len(prefix_sum)):
                L_sum = prefix_sum[j] - prefix_sum[j-L]
                max_sum = max(max_sum, L_sum + M_sum)

        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        lhash, mhash = dict(), dict()
        for i in range(len(A) - L + 1):
            if i == 0:
                lhash[i] = sum(A[:L])
            else:
                lhash[i] = lhash[i - 1] - A[i - 1] + A[i + L -1]
                
        for i in range(len(A) - M + 1):
            if i == 0:
                mhash[i] = sum(A[:M])
            else:
                mhash[i] = mhash[i - 1] - A[i - 1] + A[i + M - 1]
                
        res = 0
        for i in range(0 , len(A) - L + 1):
            if i > len(A) - M:
                break
            for j in range(i + L - 1 + 1, len(A) - M + 1 ):
                res = max(res, lhash[i] + mhash[j])
        
        for j in range(0, len(A) - M + 1):
            if j > len(A) - L:
                break
                
            for i in range(j + M - 1 + 1, len(A) - L + 1):
                res = max(res, lhash[i] + mhash[j])
                
        return res        

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        ans = 0
        sub1 = 0
        for i in range(L-1):
            sub1 += A[i]
        for i in range(L-1, len(A)):
            sub1 += A[i]
            if i >= L+M-1:
                sub2 = 0
                for j in range(M-1):
                    sub2 += A[j]
                for j in range(M-1, i-L+1):
                    sub2 += A[j]
                    ans = max(ans, sub1+sub2)
                    sub2 -= A[j-M+1]
            
            if i <= len(A)-M-1:
                sub2 = 0
                for j in range(i+1, i+M):
                    sub2 += A[j]
                for j in range(i+M, len(A)):
                    sub2 += A[j]
                    ans = max(ans, sub1+sub2)
                    sub2 -= A[j-M+1]
            sub1 -= A[i-L+1]
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix_sum, current_sum = [], 0
        
        for num in A:
            current_sum += num 
            prefix_sum.append(current_sum)
        #print(prefix_sum)
        
        i, j = -1, L-1
        max_m, sub = float('-inf'), 0
        sum_l, max_tot = 0, 0
        while j < len(prefix_sum):
            sum_l = prefix_sum[j] - sub
            sum_m = max(self.findM(prefix_sum[:i+1], M, 0),self.findM(prefix_sum[j+1:], M, prefix_sum[j]))
            max_tot = max(max_tot, sum_m+sum_l)
            i += 1
            j += 1
            sub = prefix_sum[i]                
    
        return max_tot
               
    
    def findM(self, prefix_sum, M, sub):
        if not prefix_sum or len(prefix_sum) < M:
            return 0
        max_m = float('-inf')
        sum_m = 0
        i, j = -1, M-1
        while j < len(prefix_sum):
            sum_m = (prefix_sum[j] - sub)
            i += 1
            j += 1
            sub = prefix_sum[i]            
            max_m = max(sum_m, max_m)
            #print(sum_m, prefix_sum)
        return max_m

from typing import List

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        sum_up_to = [0]
        total = 0
        for n in A:
            total += n
            sum_up_to.append(total)
        lsum = []
        msum = []
        for i in range(1,len(A)+1):
            if i >= L:
                lsum.append(sum_up_to[i]-sum_up_to[i-L])
            else:
                lsum.append(None)
            
            if i >= M:
                msum.append(sum_up_to[i]-sum_up_to[i-M])
            else:
                msum.append(None)
        
        max_sum = 0
        for i in range(len(lsum)):
            if lsum[i] is None:
                continue
            for j in list(range(i-L))+list(range(i+M, len(msum))):
                if msum[j] is None:
                    continue
                max_sum = max(max_sum, lsum[i]+msum[j])
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        # for each array of length L we need to find the max sum array of length M
        # we keep an array of cummulative sum so that we do not need to calculate them again and again
        if L+M > len(A):
            # no such array is possible
            return 0
        answer = [0]
        max_sum = -float('inf')
        for i in range(len(A)):
            answer.append(answer[-1] + A[i])
        for i in range(len(A)-L+1):
            if i >= M:
                # then only we can find non overlapping subarray in the beginning 
                for j in range(i-M+1):
                    # print(i,j, answer[i+L] - answer[i], answer[j+M] - answer[j])
                    max_sum = max(max_sum,answer[i+L] - answer[i] + answer[j+M] - answer[j])
            if i + L <= len(A) - M:
                # then only we can find non overlapping subarray in the end 
                for j in range(i + L, len(A) - M + 1):
                    # print(i,j,answer[i+L] - answer[i], answer[j+M] - answer[j])
                    max_sum = max(max_sum,answer[i+L] - answer[i] + answer[j+M] - answer[j])
            
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        cumsums = []
        cumsum = 0
        cumsums.append(cumsum)
        for num in A:
            cumsum += num
            cumsums.append(cumsum)
        n = len(A)
        ans = -float('inf')
        print(cumsums)
        for i in range(0, n - L - M + 1):
            for j in range(i + L, n - M + 1):
                ans = max(ans, cumsums[i + L] - cumsums[i] + cumsums[j + M] - cumsums[j])
        for i in range(0, n - M - L + 1):
            for j in range(i + M, n - L + 1):
                ans = max(ans, cumsums[i + M] - cumsums[i] + cumsums[j + L] - cumsums[j])
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if L + M == len(A):
            return sum(A)
        
        max_sum2 = 0
        cur_sum2 = 0
        total_len = len(A)
        
        def find_max_subarray(start_idx, end_idx, l):
            
            nonlocal A
            max_sum = 0
            cur_sum = 0
            for idx in range(start_idx, l + start_idx):
                max_sum += A[idx]
            cur_sum = max_sum
            
            for idx in range(l + start_idx, end_idx):
                cur_sum = cur_sum + A[idx] - A[idx - l]
                max_sum = max(max_sum, cur_sum)
            return max_sum
        
        cur_sum2 = 0
        for idx in range(L):
            cur_sum2 += A[idx]
        
        max_sum2 = cur_sum2 + find_max_subarray(L, total_len, M)
        
        for idx in range(L, total_len - M):
            cur_sum2 = cur_sum2 + A[idx] - A[idx - L]
            max_sum2 = max(max_sum2, cur_sum2 + find_max_subarray(idx+1, total_len, M))
        
        if L != M:
            cur_sum2 = 0
            for idx in range(M):
                cur_sum2 += A[idx]
            max_sum2 = max(max_sum2, cur_sum2 + find_max_subarray(M, total_len, L))
            for idx in range(M, total_len - L):
                cur_sum2 = cur_sum2 + A[idx] - A[idx - M]
                max_sum2 = max(max_sum2, cur_sum2 + find_max_subarray(idx+1, total_len, L))
        
        return max_sum2


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        preSum = [0]
        acc = 0
        for i in range(len(A)):
            acc += A[i]
            preSum.append(acc)
        #preSum[j] = A[0] + A[1] + ...+ A[j - 1]
        # preSum[j] - preSum[i] = A[j - 1] + ... + A[i] length = j - i
        # preSum[i] - preSum[i - L] = A[i - 1] + .... + A[i - L]
        # preSum[j + M] - preSum[j] = A[j + M - 1] + ...+ A[j]
        mx = 0
        for i in range(L, len(preSum)):
            for j in range(i, len(preSum) - M):
                left = preSum[i] - preSum[i - L]
                right = preSum[j + M] - preSum[j]
                mx = max(mx, left + right)
        for i in range(M, len(preSum)):
            for j in range(i, len(preSum) - L):
                left = preSum[i] - preSum[i - M]
                right = preSum[j + L] - preSum[j]
                mx = max(mx, left + right)
        return mx


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        ans = 0
        for f, l in zip([L, M], [M, L]):
            max_first = first = sum(A[:f])
            ans = max(ans, first + sum(A[f:f+l]))
            for i in range(f, len(A) - l):
                first = first + A[i] - A[i-f]
                max_first = max(max_first, first)
                ans = max(ans, max_first + sum(A[i+1:i+1+l]))
        
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        sums = list(itertools.accumulate(A))
        def get_sums(n):
            return [(sums[i]-sums[i-n] if i-n >= 0 else sums[i], i-n+1, i) for i in range(n-1, len(sums))]
            
        l_sums = get_sums(L)
        m_sums = get_sums(M)
        max_sum = float('-inf')
        for l_sum, l_i, l_j in l_sums:
            for m_sum, m_i, m_j in m_sums:
                if m_j < l_i or l_j < m_i:
                    max_sum = max(max_sum, m_sum + l_sum)
        
        return max_sum
        
        
        # we know there will be len - (L+M) elements excluded
        # there will a stretch between before them
        # iterate through looking for the larger array sum
        # search in the left and right remainders for the smaller array sum of size x


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        '''
        Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
        9 + (6+5) = 20
        
         A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
         (8+9)+ (3+8+1) = 29
         
         A = [3,8,1,3,2,1,8,9,3], L = 3, M = 2
         (3+8)+(8+9+3) = 31
         
         3,8,1 + 3,2
         3,8,1 + 2,1
         - try all possibilities (A[i:i+L], A[i+L: i+L+M]) (A[i:i+M], A[i+M: i+L+M])
         - get the max value
         - memoize 
         
         L = 3 M = 2
         preprocess
         [0, 6, 11, 13, 15, 20, 21, 30, 34]
                             ^           ^
          (11-0)+(20-11)=20
          (11-0)+(21-13)=19
          (11-0)+(21-13)=19
          (11-0)+(30-15)=26
          (11-0)+(34-20)=25
          
          (13-0)+(21-13)=21
          (13-0)+(30-15)=28
          (13-0)+(30-20)=23
          (13-0)+(30-20)=23
          
          (15-6)+(30-15)=24
          (15-6)+(34-20)=23
          
          (20-11)+(34-20)=23
          
          O(n^2)
          
          0 6 5 2 2 5 1 9 4, 1, 2
          
        '''
        
        arr = self.preprocess(A)
        def helper(arr, n1, n2):
            max_val = 0
            for i in range(n1-1, len(arr)-n2):
                for j in range(i+n2, len(arr)):
                    val1 = arr[i] if i-n1 < 0 else arr[i]-arr[i-n1]
                    val2 = arr[j]-arr[j-n2]
                    max_val = max(val1+val2, max_val)
            return max_val
        
        return max(helper(arr, L, M), helper(arr, M, L))
    
    def preprocess(self, A):
        total = 0
        result = [0 for _ in range(len(A))]
        for i in range(len(A)):
            total+=A[i]
            result[i]=total
        return result

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        self.cum = [A[0]]
        
        for i in range(1, len(A)):
            self.cum.append(self.cum[i-1] + A[i])
            
        largest = 0
        for i in range(len(A) - L + 1):
            l_sum = self.cum[i+L-1] - self.cum[i] + A[i]
            m_sum = 0
            for j in range(i - M + 1):
                m_sum = max(m_sum, self.cum[j+M-1] - self.cum[j] + A[j])

            for j in range(i+L, len(A) - M +1):
                m_sum = max(m_sum, self.cum[j+M-1] - self.cum[j] + A[j])

            largest = max(largest, l_sum + m_sum)
                
        
        return largest


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        l=len(A)
        presum=[0]*(l+1)
        for i in range(l):
            presum[i+1]=presum[i]+A[i]
        if L<M:
            M,L=L,M
        ans=0
        for i in range(l-L+1):
            tmp=presum[i+L]-presum[i]
            j=0
            while j<(l-M+1):
                if i<j+M<i+L:
                    j=i+L
                else:
                    ans=max(ans,tmp+presum[j+M]-presum[j])
                    j+=1
                    
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        '''
            [0,6,5,2,2,5,1,9,4]
            
            [0,6,11,13,15,20,21,30,34]
                       i i
            
            max_sum = -?
        
        '''
        
        summ = 0
        
        for i in range(len(A)):
            summ += A[i]
            A[i] = summ
        
        
        max_sum = -float('inf')
        for i in range(len(A) - L + 1):
            if i - 1 > -1:
                L_sum = A[i+L - 1] - A[i - 1]
            else:
                L_sum = A[i+L - 1]
            M_max_sum = -float('inf')
            for j in range(i - M + 1):
                if j - 1 > -1:
                    M_sum = A[j+M-1] - A[j - 1]
                else:
                    M_sum = A[j+M-1]
                M_max_sum = max(M_max_sum, M_sum)
            
            for j in range(i+L, len(A) - M + 1):
                if j - 1 > -1:
                    M_sum = A[j+M-1] - A[j - 1]
                else:
                    M_sum = A[j+M-1]
                M_max_sum = max(M_max_sum, M_sum)
            
            max_sum = max(max_sum, L_sum + M_max_sum)
        
        
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        presum = [0]
        for a in A:
            presum.append(presum[-1] + a)
            
        def helper(A, l1, l2):
            res = 0
            N = len(A)
            for i in range(N - l1 + 1 - l2):
                for j in range(i + l1, N - l2 + 1):
                    s1 = presum[i + l1 - 1 + 1] - presum[i]
                    s2 = presum[j + l2 - 1 + 1] - presum[j]
                    res = max(res, s1 + s2)
            
            return res
        
        r1 = helper(A, L, M)
        r2 = helper(A, M, L)
        return max(r1, r2)


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        cur_max_l = max_l = sum(A[:L])
        ans = max_l + sum(A[L:L+M])
        
        for i in range(L, len(A) - M):
            cur_max_l = cur_max_l + A[i] - A[i-L]
            max_l = max(max_l, cur_max_l)
            
            ans = max(ans, max_l + sum(A[i+1:i+1+M]))
        
        cur_max_m = max_m = sum(A[:M])
        ans = max(ans, max_m + sum(A[M:L+M]))
        
        for i in range(M, len(A) - L):
            cur_max_m = cur_max_m + A[i] - A[i-M]
            max_m = max(max_m, cur_max_m)
            
            ans = max(ans, max_m + sum(A[i+1:i+1+L]))
        
        return ans

from itertools import accumulate
from functools import lru_cache
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L0: int, M0: int) -> int:
        #lru_cache(None)
        def range_sum(i,j):
            return accum[j-1] - (accum[i-1] if i > 0 else 0)
        if not A:
            return 0
        max_sum = 0
        accum = list(accumulate(A,lambda x,y:x+y))
        for L,M in ((L0,M0),(M0,L0)):
            for i in range(len(A)-L+1):
                sum1 = range_sum(i,i+L)
                for j in range(i+L,len(A)-M+1):
                    sum2 = range_sum(j,j+M)      
                    max_sum = max(max_sum, sum1+sum2)
        return max_sum
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        cumul = [0]
        for a in A:
            cumul.append(cumul[-1] + a)
            
        best = 0
        for i in range(len(A) - L - M + 1):
            for j in range(i + L, len(A) - M + 1):
                best = max(best, cumul[i + L] - cumul[i] + cumul[j + M] - cumul[j])
            for j in range(i + M, len(A) - L + 1):
                best = max(best, cumul[i + M] - cumul[i] + cumul[j + L] - cumul[j])
        return best

from itertools import accumulate
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L0: int, M0: int) -> int:
        def range_sum(i,j):
            return accum[j-1] - (accum[i-1] if i > 0 else 0)
        if not A:
            return 0
        max_sum = 0
        accum = list(accumulate(A,lambda x,y:x+y))
        for L,M in ((L0,M0),(M0,L0)):
            for i in range(len(A)-L+1):
                sum1 = range_sum(i,i+L)
                for j in range(i+L,len(A)-M+1):
                    sum2 = range_sum(j,j+M)      
                    max_sum = max(max_sum, sum1+sum2)
        return max_sum
                


from itertools import accumulate
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L0: int, M0: int) -> int:
        def range_sum(i,j):
            return accum[j-1] - (accum[i-1] if i > 0 else 0)
        
        if not A:
            return 0
        max_sum = 0
        accum = list(accumulate(A,lambda x,y:x+y))
        for L,M in ((L0,M0),(M0,L0)):
            for i in range(len(A)-L+1):
                sum1 = range_sum(i,i+L)
                for j in range(i+L,len(A)-M+1):
                    sum2 = range_sum(j,j+M)      
                    max_sum = max(max_sum, sum1+sum2)
        return max_sum
                


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if len(A)< M+L:
            return -1
        
        def getSumM(start, end):
            if end-start<M:
                return 0
            preSumM=sum(A[start:start+M])
            maxM=preSumM
            for i in range(start+1,end-M+1):
                preSumM=preSumM-A[i-1]+A[i+M-1]
                maxM=max(maxM,preSumM)
            return maxM
            
        preSumL=sum(A[:L-1])
        maxSum=-sys.maxsize
        for i in range(len(A)-L+1):
            preSumL=preSumL+A[i+L-1]
            leftSumM=getSumM(0,i)
            rightSumM=getSumM(i+L,len(A))
            maxSum= max(maxSum,preSumL+max(leftSumM,rightSumM))
            preSumL=preSumL-A[i]
        return maxSum
        


class Solution:
    def maxSumTwoNoOverlap(self, arr: List[int], L: int, M: int) -> int:
        Lsum = [0]*len(arr)
        Msum = [0]*len(arr)
        
        def makeWindow(arr,res,size):
            window = 0
            for i in range(0,size):
                window += arr[i]
            res[i] = window
            
            for i in range(size,len(arr)):
                res[i] = res[i-1] -arr[i-size] +arr[i]
            

        makeWindow(arr,Lsum,L)
        makeWindow(arr,Msum,M)
        
        res = 0
        for i in range(L-1,len(arr)):
            for j in range(0,i-L):
                res = max(res,Lsum[i]+Msum[j])
            for j in range(i+M,len(arr)):
                res = max(res,Lsum[i]+Msum[j])
        
        return res


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        '''
        1. create cumsum arr
        2. create arr of subarry sums from cumsum for L and M
        3. N^2 mix and match while ensuring the nums don't overlap
        
        '''
        
        cumsum = []
        for num in A:
            if not cumsum:
                cumsum.append(num)
            else:
                cumsum.append(cumsum[-1]+num)
        
        Lsums = [0]*len(A)
        Msums = [0]*len(A)
        
        if M>L:
            L,M = M,L # makes M smaller
        
        for j in range(L-1,len(A)):
            if j==L-1:
                Lsums[j] = cumsum[j]
            else:
                Lsums[j] = cumsum[j]-cumsum[j-L]
        for j in range(M-1,len(A)):
            if j==M-1:
                Msums[j] = cumsum[j]
            else:
                Msums[j] = cumsum[j]-cumsum[j-M]
        
        out = 0
        for l in range(L-1,len(A)):
            for m in range(M-1,len(A)):
                # M is before L completely
                # M is after L completely
                if m <= l-L or m-M>=l:
                    out = max(out,Lsums[l]+Msums[m])
        return out

from typing import List
class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix_sums = [0]
        current_sum = 0
        for right in range(len(A)):
            current_sum += A[right]
            prefix_sums.append(current_sum)
        # print(prefix_sums)
        best = 0
        left = 0
        memo = dict()
        while left+L <= len(A) and left+L < len(prefix_sums):
            limits = ((0, left), (left+L, len(prefix_sums)))
            best_m = self.get_max_subarray(prefix_sums, M, limits, memo)
            subarray_sum = best_m[0] + prefix_sums[left+L]-prefix_sums[left]
            # if subarray_sum > best:
            #     print(f'{A[best_m[1]:best_m[2]]}={best_m[0]}')
            #     print(f'{A[left:left+L]}={subarray_sum-best_m[0]}')
            best = max(best, subarray_sum)
            left += 1
        return best

    def get_max_subarray(self, sums, length, limits, memo):
        # stores highest sum as tuple of (sum, left, right (exclusive))
        if (length, limits) in memo:
            return memo[(length, limits)]
        high_score = (0,0,0)
        for limit in limits:
            left = limit[0]
            # test subarrays of length within limit[0] and limit[1] (excluding limit[1])
            while left + length <= limit[1] and left + length < len(sums):
                subarray_sum = sums[left+length] - sums[left]
                # print(f'{left}:{left+length}={subarray_sum}')
                high_score = max(high_score, (subarray_sum, left, left+length))
                # print(f'high: {high_score}')
                left+=1
        memo[(length, limits)] = high_score
        return high_score


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix = [0]
        for num in A:
            prefix.append(num+prefix[-1])
        n = len(A)
        ans = 0

        for i in range(n-L+1):
            a = prefix[i+L]-prefix[i]
            for j in range(n-M+1):
                if j+M<=i or i+L<=j:
                    b = prefix[j+M]-prefix[j]
                    ans = max(ans, a+b)
        return ans

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        def solve(arr, la, lb):
            n = len(arr)
            post = [0] * n
            pre = [0] * n
            ans = 0

            curr = 0
            for i in range(n-1, -1, -1):
                curr += arr[i]
                if i < n-lb:
                    curr -= arr[i+lb]
                    post[i] = max(curr, post[i+1]) 
                else:
                    post[i] = curr

            curr = 0
            for i in range(n):
                curr += arr[i]
                if i >= la:
                    curr -= arr[i-la]
                    pre[i] = max(curr, pre[i-1])
                else:
                    pre[i] = curr
                if i < n-1:
                    ans = max(ans, pre[i] + post[i+1])

            return ans
        
        return max(solve(A, L, M), solve(A, M, L))


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        N = len(A)
        sum_l = [sum(A[i:i+L]) for i in range(N-L+1)]
        sum_m = [sum(A[i:i+M]) for i in range(N-M+1)]
        
        max_sum = 0
        for i in range(len(sum_l)):
            for j in range(len(sum_m)):
                if (i <= j and j < (i+L)) or (i >= j and i < (j+M)):
                    continue
                max_sum = max(max_sum, sum_l[i]+sum_m[j])
                
        return max_sum

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        temp, prefix_sums  = 0, [0]
        N = len(A)        
        maxsum = 0
        
        # define prefix_sums[i] as: A[0] + A[1] + ... + A[i-1]
        for i in range(N):
            prefix_sums.append(temp + A[i])
            temp += A[i]
        # the last subarray = A[i] + A[i+1] +  ... + A[N-1], so maximum i = N - L
        for i in range(0, N - L + 1):
            for j in range(0, i - M + 1):
                # print(\"i=\",i,\"; j=\",j)
                if j < 0:
                    continue
                sum1 = prefix_sums[i + L] - prefix_sums[i]
                sum2 = prefix_sums[j + M] - prefix_sums[j]
                maxsum = max(maxsum, sum1+sum2)
           
            for j in range(i + L, N - M + 1):
                # print(\"i=\",i,\"; j=\",j)
                if j + M -1 >= N:
                    continue
                sum1 = prefix_sums[i + L] - prefix_sums[i]
                sum2 = prefix_sums[j + M] - prefix_sums[j]
                maxsum = max(maxsum, sum1+sum2)         
            
        return maxsum


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        l_sums = []
        m_sums = []
        flag_l = 0
        flag_m = 0
        
        l_sum_tmp = 0
        r_sum_tmp = 0
        for i in range(len(A)):
            if flag_l < L:
                flag_l += 1
                l_sum_tmp += A[i]
            else:
                l_sums.append(l_sum_tmp)
                l_sum_tmp += A[i] - A[i-L]
            
            if flag_m < M:
                flag_m += 1
                r_sum_tmp += A[i]
            else:
                m_sums.append(r_sum_tmp)
                r_sum_tmp += A[i] - A[i-M]
        m_sums.append(r_sum_tmp)
        l_sums.append(l_sum_tmp)
        
        max_sum = -1
        for i in range(len(m_sums)):
            for j in range(len(l_sums)):
                if i+M<=j or j+L<=i:
                    # print(m_sums[i], l_sums[j])
                    max_sum = max(m_sums[i]+l_sums[j], max_sum)
                    
        return max_sum
            
        
        return 1


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        sum_l = []
        sum_m = []
        for i in range(len(A) - L + 1):
            sum_l.append(sum(A[i: i+L]))
        for i in range(len(A) - M + 1):
            sum_m.append(sum(A[i: i+M]))
        res = 0
        for i in range(len(A) - L + 1):
            for j in range(len(A) - M + 1):
                if i + L <= j or i >= j + M:
                    res = max(res, sum_l[i] + sum_m[j])
        return res

class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        if L + M == len(A):
            return sum(A)
        
        prefixSums = [0] * len(A)
        prefixSums[0] = A[0]
        for i in range(1, len(A)):
            prefixSums[i] = prefixSums[i-1] + A[i]
        #print(prefixSums)            

        maxSum = -1
        tempSum = None
        secondTemp = None
        for i in range(0, len(A) - L + 1):
            if i == 0:
                tempSum = prefixSums[i + L - 1]
            else:
                tempSum = prefixSums[i + L - 1] - prefixSums[i - 1]
                
            for j in range(0, len(A) - M + 1):
                if j + M - 1 < i or j > i + L - 1:
                    if j == 0:
                        secondTemp = prefixSums[j + M - 1]
                    else:
                        secondTemp = prefixSums[j + M - 1] - prefixSums[j - 1]
                  
                    if maxSum < tempSum + secondTemp:
                        maxSum = tempSum + secondTemp
                
        return maxSum


class Solution:
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        la = []
        ma = []
        i = 0
        for i in range(len(A) - L + 1):
            la.append(sum(A[i:i+L]))
        for i in range(len(A) - M + 1):
            ma.append(sum(A[i:i+M]))
        print((la, ma))
        maxi = 0
        for i in range(len(la)):
            for j in range(len(ma)):
                if i < j:
                    if i + L > j:
                        continue
                if j < i:
                    if j + M > i:
                        continue
                if j == i:
                    continue
                maxi = max(maxi, la[i]+ma[j])
                        
        return maxi
            
        


class Solution:
    def maxSubarrayOfLengthK(self,A,start,end,K):
        if end-start < K:
            return (float('-inf'),0,len(A)+1)
        total_sum  = 0
        for i in range(start,start+K):
            total_sum += A[i]
        
        opt_sum = (total_sum,start,start+K-1)
        
        for j in range(start+K,end):
            total_sum += (A[j]-A[j-K])
            if total_sum > opt_sum[0]:
                opt_sum = (total_sum,j-K+1,j)
        return opt_sum
            
    
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        prefix_sums = [0 for _ in A+[0]]
        
        for i in range(1,len(A)+1):
            prefix_sums[i] = A[i-1] + prefix_sums[i-1]
        
        def solve(prefix_sums,L,M):
            res = 0
            for i in range(len(A)-L):
                total_sum = prefix_sums[i+L] - prefix_sums[i]
                l1,r1 = 0,i
                l2,r2 = i+L,len(A)
                other = max(self.maxSubarrayOfLengthK(A,l1,r1,M)[0],self.maxSubarrayOfLengthK(A,l2,r2,M)[0])
                res = max(total_sum+other,res)

            return res
        
        return max(solve(prefix_sums,L,M),solve(prefix_sums,M,L))

class Solution:
    def maxWindowSum(self, A, M):
        acc = [A[0]]
        for i in range(1, len(A)):
            acc.append(acc[i-1] + A[i])
        maxSum = sum(A[:M])
        for i in range(M, len(A)):
            maxSum = max(maxSum, acc[i] - acc[i-M])
        return maxSum
            
    def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
        n = len(A)
        if not A or L+M > n:
            return 0
        left = []
        right = []
        maxSum = 0
        for i in range(n - L + 1):
            maxL = sum(A[i:i+L])
            maxM = 0
            if i >= M:
                left = A[:i]
                maxM = max(maxM,self.maxWindowSum(left, M))
            if n - i - L >= M:
                right = A[i+L:]
                maxM = max(maxM, self.maxWindowSum(right, M))
                
            maxSum = max(maxSum, maxL + maxM)
        return maxSum