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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Amortized analysis

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):
			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):
			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)]
		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]
		result = 0
		for i in range(len(A) - L - M + 1):
			sub1 = get_subsum(i, i + L - 1)
			for j in range(i + L, len(A) - M + 1):
				sub2 = get_subsum(j, j + M - 1)
				result = max(result, sub1 + sub2)
		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:
		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:
				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):
				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
		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]
			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)
		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:
		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])
			left = A[:i]
			right = A[i + long:]
			if len(left) >= short:
				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:
		n = len(A)
		if L + M == n:
			return sum(A)
		cumsum = [0] * (n + 1)
		for i in range(n):
			cumsum[i + 1] = cumsum[i] + A[i]

		def good_combo(i, 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)))
		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)
		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])
		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))
		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:
		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


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


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:
		(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


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


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:
		n = len(A)
		dp = [[0, 0] for _ in range(n)]
		for i in range(L - 1, n):
			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):
			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]
		maximum = float('-inf')
		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
			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)
		Lsum.sort(reverse=True)
		Msum = get_subsum(M)
		Msum.sort(reverse=True)

		def overlap(i, j, L=L, M=M):
			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)
			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))
		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:
				for k in range(M - 1, i - L):
					result = max(result, lsum + prefix[k])
		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
		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])
		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))]
		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
		maxSum = -math.inf
		for (i, sums) in enumerate(dp):
			if sums[0] == -1:
				continue
			eligible_M = dp[:i - L + 1] + dp[i + M:]
			maxSum = max(maxSum, sums[0] + max(eligible_M, key=lambda x: x[1])[1])
		return maxSum


class Solution:

	def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
		N = len(A)
		prefix = [0] * (N + 1)
		for i in range(1, N + 1):
			prefix[i] = prefix[i - 1] + A[i - 1]
		res = 0
		for Li in range(N - L + 1):
			Lj = Li + L
			sumL = prefix[Lj] - prefix[Li]
			sumM = 0
			for Mi in range(Lj, N - M + 1):
				Mj = Mi + M
				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):
			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]
		for i in range(len(A) - L + 1):
			lSum = cumulatedSum[i + L] - cumulatedSum[i]
			for j in range(i + L, len(A) - 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]
		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:
		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
		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:
		A = [0] + A
		for i in range(1, len(A)):
			A[i] += A[i - 1]

		def solve(l, m, a):
			curr = 0
			for i in range(len(a) - l + 1):
				for j in range(i + l, len(a) - m):
					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 max(m, m2)


class Solution:

	def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
		N = len(A)
		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
		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)
		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:
		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:
		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
		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)
		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)
		(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)
		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:
		if L + M > len(A):
			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:
				for j in range(i - M + 1):
					max_sum = max(max_sum, answer[i + L] - answer[i] + answer[j + M] - answer[j])
			if i + L <= len(A) - M:
				for j in range(i + L, len(A) - M + 1):
					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)
		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


class Solution:

	def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
		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:
		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:

		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


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:
		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)
		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)):
				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)
		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]
			best = max(best, subarray_sum)
			left += 1
		return best

	def get_max_subarray(self, sums, length, limits, memo):
		if (length, limits) in memo:
			return memo[length, limits]
		high_score = (0, 0, 0)
		for limit in limits:
			left = limit[0]
			while left + length <= limit[1] and left + length < len(sums):
				subarray_sum = sums[left + length] - sums[left]
				high_score = max(high_score, (subarray_sum, left, left + length))
				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
		for i in range(N):
			prefix_sums.append(temp + A[i])
			temp += A[i]
		for i in range(0, N - L + 1):
			for j in range(0, i - M + 1):
				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):
				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:
					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]
		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