1031. Maximum Sum of Two Non-Overlapping Subarrays

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.

class Solution {
    int helper(vector<int>& nums, int firstLen, int secondLen) {
        vector<int> f{0};
        vector<int> psum{0};
        int res = 0;
        for(int i = 0; i < nums.size(); i++) {
            psum.push_back(psum.back() + nums[i]);
            int sz = psum.size();
            if(sz >= firstLen + 1) {
                f.push_back(max(f.back(), psum.back() - psum[sz - firstLen - 1]));
            } else {
                f.push_back(0);
            }
            if(sz >= secondLen + firstLen) {
                res = max(res, psum.back() - psum[sz - secondLen - 1] + f[sz - secondLen - 1]);
            }
        }
        return res;
    }
public:
    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
        return max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
    }
};