Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen.

The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping.

A subarray is a contiguous part of an array.

&nbsp;
Example 1:

Input: nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.


Example 2:

Input: nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.


Example 3:

Input: nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [0,3,8] with length 3.


&nbsp;
Constraints:


	1 &lt;= firstLen, secondLen &lt;= 1000
	2 &lt;= firstLen + secondLen &lt;= 1000
	firstLen + secondLen &lt;= nums.length &lt;= 1000
	0 &lt;= nums[i] &lt;= 1000


class Solution:
    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:
        n = len(nums)
        p = [0]
        for el in nums:
            p.append(p[-1] + el)
        msum = 0
        for f, s in [(firstLen, secondLen), (secondLen, firstLen)]:
            for i in range(f - 1, n - s + 1):
                for j in range(i + 1, n - s + 1):
                    l = p[i + 1] - p[i - f + 1]
                    r = p[j + s] - p[j]
                    msum = max(msum, l + r)
        return msum
class Solution {
    public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
        int []dp1=new int[nums.length];
        int []dp2=new int[nums.length];
        
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(i<firstLen){
                sum+=nums[i];
                dp1[i]=sum;
            }else{
                sum+=nums[i]-nums[i-firstLen];
                dp1[i]=Math.max(sum,dp1[i-1]);
            }
        }
        
        sum=0;
        for(int i=nums.length-1;i>=0;i--){
            if(i+secondLen>=nums.length){
                sum+=nums[i];
                dp2[i]=sum;
            }else{
                sum+=nums[i]-nums[i+secondLen];
                dp2[i]=Math.max(sum,dp2[i+1]);
            }
        }
        
        int max=0;
        
        for(int i=firstLen-1;i<nums.length-secondLen;i++){
            max=Math.max(max,dp1[i]+dp2[i+1]);
        }
        
        int max1=max;
        
        dp1=new int[nums.length];
        dp2=new int[nums.length];
        
        sum=0;
        for(int i=0;i<nums.length;i++){
            if(i<secondLen){
                sum+=nums[i];
                dp1[i]=sum;
            }else{
                sum+=nums[i]-nums[i-secondLen];
                dp1[i]=Math.max(sum,dp1[i-1]);
            }
        }
        
        sum=0;
        for(int i=nums.length-1;i>=0;i--){
            if(i+firstLen>=nums.length){
                sum+=nums[i];
                dp2[i]=sum;
            }else{
                sum+=nums[i]-nums[i+firstLen];
                dp2[i]=Math.max(sum,dp2[i+1]);
            }
        }
        
        max=0;
        
        for(int i=secondLen-1;i<nums.length-firstLen;i++){
            max=Math.max(max,dp1[i]+dp2[i+1]);
        }
        
        
        int max2=max;
        
        return Math.max(max1,max2);
    }
}
class Solution {
public:
    
    int solve(vector<int>& prefixSum, int n, int firstLen, int secondLen){
        vector<int> dp(n, 0);
        
        dp[n-secondLen] = prefixSum[n]-prefixSum[n-secondLen];
        
        for(int i=n-secondLen-1; i>=0; i--){
            dp[i] = max(dp[i+1], prefixSum[i+secondLen]-prefixSum[i]);
        }
        
        dp[firstLen] = dp[firstLen] + prefixSum[firstLen]-prefixSum[0];
        
        for(int i=firstLen+1; i<=n-secondLen; i++){
            dp[i] = max(dp[i-1], dp[i] + (prefixSum[i]-prefixSum[i-firstLen]));
        }
        
        return *max_element(dp.begin(), dp.end());
    }
    
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        int n = nums.size();
        vector<int> prefixSum(n+1, 0);
        
        for(int i=1; i<=n; i++){
            prefixSum[i] = prefixSum[i-1] + nums[i-1];
        }
        
        return max(solve(prefixSum, n, firstLen, secondLen), solve(prefixSum, n, secondLen, firstLen));
    }
};
var maxSumTwoNoOverlap = function(nums, firstLen, secondLen) {
    function helper(arr, x, y)
    {
        const n = arr.length;
        let sum = 0;
        const dp1 = []; // store left x sum
        const dp2 = []; // store right y sum

        for(let i = 0; i<n; i++)
        {
            if(i<x) {
                sum += arr[i];
                dp1[i] = sum;
            }
            else {
                sum += arr[i] - arr[i-x];
                dp1[i] = Math.max(dp1[i-1], sum);
            }
        }
        sum = 0;
        for(let i = n-1; i>=0; i--)
        {
            if(i>=n-y)
            {
                sum += arr[i];
                dp2[i] = sum;
            }
            else
            {
                sum += arr[i] - arr[i+y];
                dp2[i] = Math.max(dp2[i+1], sum);
            }
        }
        let max = -Infinity;
        for(let i = x-1; i< n-y; i++)
        {
            max = Math.max(max, dp1[i] + dp2[i+1]);
        }
        return max;
    }
    return Math.max(helper(nums, firstLen, secondLen), 
                   helper(nums, secondLen, firstLen));
};
Maximum Sum of Two Non-Overlapping Subarrays