Solution

Method 1 – Sliding Window for Both Orders

Intuition

To maximize the sum of two non-overlapping subarrays, try both possible orders: firstLen before secondLen and secondLen before firstLen. For each order, use sliding windows to track the best sum for the first subarray and combine it with the current sum of the second subarray.

Approach

For both orders (firstLen before secondLen and vice versa):
- Use a sliding window to compute the sum of the first subarray and keep track of the maximum sum so far.
- For each position, compute the sum of the second subarray and add the best sum of the first subarray that does not overlap.
Return the maximum sum found among both orders.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {\n        return max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));\n    }\n    int helper(vector<int>& nums, int l, int r) {\n        int n = nums.size(), ans = 0, maxL = 0, sumL = 0, sumR = 0;\n        for (int i = 0; i < l + r; ++i) sumR += nums[i];\n        for (int i = 0; i < l; ++i) sumL += nums[i];\n        maxL = sumL;\n        for (int i = l; i < l + r; ++i) sumR += nums[i] - nums[i - r];\n        ans = max(ans, maxL + sumR);\n        for (int i = l + r; i < n; ++i) {\n            sumL += nums[i - r] - nums[i - r - l];\n            maxL = max(maxL, sumL);\n            sumR += nums[i] - nums[i - r];\n            ans = max(ans, maxL + sumR);\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maxSumTwoNoOverlap</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-d

Related Tags