# 1031. Maximum Sum of Two Non-Overlapping Subarrays
###### tags: `Leetcode` `Medium` `Prefix Sum` `Sliding Window`
Link: https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/description/
## 思路
思路参考[这里](https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/solutions/279221/java-python-3-two-easy-dp-codes-w-comment-time-o-n-no-change-of-input/)
分情况讨论 firstLen在左边和firstLen在右边的情况
随着指针移动 记录左边的array的最大值 用最大值加上右边的array的sum 以此找最大值
## Code
Prefix Sum

class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int n = nums.length;
        int[] prefixSum = new int[n+1];
        for(int i=0; i<n; i++) prefixSum[i+1] = prefixSum[i]+nums[i];
        return Math.max(maxSum(prefixSum, firstLen, secondLen), maxSum(prefixSum, secondLen, firstLen));
    }
    public int maxSum(int[] prefixSum, int L, int M){
        int ans = 0;
        int maxL = 0;
        for(int i=L+M; i<prefixSum.length; i++){
            maxL = Math.max(maxL, prefixSum[i-M]-prefixSum[i-M-L]);
            ans = Math.max(ans, maxL+prefixSum[i]-prefixSum[i-M]);
        }
        return ans;
    }
}

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        def maxSum(L: int, M: int):
            ans = maxL = 0
            for i in range(L+M, len(prefixSum)):
                maxL = max(maxL, prefixSum[i-M]-prefixSum[i-M-L])
                ans = max(ans, maxL+prefixSum[i]-prefixSum[i-M])
            return ans

        prefixSum = [0]*(len(nums)+1)
        for i, a in enumerate(nums):
            prefixSum[i+1] = prefixSum[i]+a
        return max(maxSum(firstLen, secondLen), maxSum(secondLen, firstLen))

Sliding Window

class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        def maxSum(L: int, M: int):
            sumL = sumM = 0
            for i in range(0, L+M):
                if i<L: sumL += nums[i]
                else: sumM += nums[i]
            maxL = sumL
            ans = sumL+sumM
            for i in range(L+M, len(nums)):
                sumL += nums[i-M]-nums[i-M-L]
                sumM += nums[i]-nums[i-M]
                maxL = max(maxL, sumL)
                ans = max(ans, maxL+sumM)
            return ans
        return max(maxSum(firstLen, secondLen), maxSum(secondLen, firstLen))