# LeetCode: 1031. 两个非重叠子数组的最大和¶

## 1、题目描述¶

• $0 <= i < i + L - 1 < j < j + M - 1 < A.length$ , 或
• $0 <= j < j + M - 1 < i < i + L - 1 < A.length.$

输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2



输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2



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



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

## 2、解题思路¶

• 因为想要取出两个连续的子数组，那么数组中可以看成有一条分界线，左面和右面分别取出一个子数组令和最大
• 首先计算几个辅助数组：
• 从左面到当前位置取出L长度子数组最大和
• 从左面到当前位置取出M长度子数组最大和
• 从右面到当前位置取出L长度子数组最大和
• 从右面到当前位置取出M长度子数组最大和
• 然后我们就从中间的分界线进行判断即可，每次取出左面和右面的最大和，更新结果即可
class Solution:
def maxSumTwoNoOverlap(self, A: List[int], L: int, M: int) -> int:
length = len(A)
ans = -1
l_left = [-1] * length
l_right = [-1] * length
m_left = [-1] * length
m_right = [-1] * length

def get_max_sub(sub_len, source, target):
pos = sub_len
cur_sums = sum(source[:sub_len])
max_sums = cur_sums
target[sub_len - 1] = cur_sums
while pos < len(source):
cur_sums = cur_sums + source[pos] - source[pos - sub_len]
max_sums = max(max_sums, cur_sums)
target[pos] = max_sums
pos += 1

get_max_sub(L, A, l_left)
get_max_sub(L, list(reversed(A)), l_right)
get_max_sub(M, A, m_left)
get_max_sub(M, list(reversed(A)), m_right)

min_sub_len = min(L, M)

for i in range(min_sub_len - 1, length - min_sub_len):
if l_left[i] != -1 and m_right[length - i - 2] != -1:
ans = max(ans, l_left[i] + m_right[length - i - 2])
if m_left[i] != -1 and l_right[length - i - 2] != -1:
ans = max(ans, m_left[i] + l_right[length - i - 2])
return ans