难度：★★★☆☆
类型：数组
方法：动态规划，前缀和
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给出非负整数数组 A ，返回两个非重叠（连续）子数组中元素的最大和，子数组的长度分别为 L 和 M。（这里需要澄清的是，长为 L 的子数组可以出现在长为 M 的子数组之前或之后。）
从形式上看，返回最大的 V，而 V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并满足下列条件之一：
0 <= i < i + L - 1 < j < j + M - 1 < A.length, 或
0 <= j < j + M - 1 < i < i + L - 1 < A.length.
示例 1：
输入：A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
输出：20
解释：子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。
示例 2：
输入：A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
输出：29
解释：子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。
示例 3：
输入：A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
输出：31
解释：子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。
提示：
L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000
解答
对于连续子数组的求和问题，我们可以使用前缀和实现快速查找和计算。而对于寻找子数组的问题，又常常使用动态规划解决。
两种情况：
第一种，L长度的子串在左边，M长度的子串在右边，两个子串各自的和分别用left_l和right_m表达，整体的和为left_l + right_m；
第二种，M长度的子串在左边，L长度的子串在右边，两个子串各自的和分别用left_m和right_l来表达，整体的和为left_m + right_l。
初始化过程，我们把left_l和left_m初始化为相应长度的前缀和，递推过程中，需要及时的更新这两个变量以及最终结果ans。
class Solution:
def maxSumTwoNoOverlap(self, A, L, M):
for i in range(1, len(A)): # 前缀和
A[i] += A[i-1]
ans, left_l, left_m = A[L + M - 1], A[L - 1] - 0, A[M - 1] - 0
for i in range(L+M, len(A)):
left_l = max(left_l, A[i - M] - A[i - M - L]) # 从i-M-L到i-M的子区间的和，长度为L
right_m = A[i] - A[i - M] # 从i-M到i的子区间的和，长度为M
left_m = max(left_m, A[i - L] - A[i - L - M]) # 从i-M-L到i-L的子区间的和，长度为M
right_l = A[i] - A[i - L] # 从i-L到i的子区间的和，长度为L
ans = max(ans, left_l + right_m, left_m + right_l) # 两种情况取最大
return ans
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
