难度：★★★☆☆
类型：数组
方法：动态规划，前缀和

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给出非负整数数组 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解决方案，请移步力扣中等题解析