1031. Maximum Sum of Two Non-Overlapping Subarrays LeetCode Solution
In this guide, you will get 1031. Maximum Sum of Two Non-Overlapping Subarrays LeetCode Solution with the best time and space complexity. The solution to Maximum Sum of Two Non-Overlapping Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
1031. Maximum Sum of Two Non-Overlapping Subarrays LeetCode Solution in C++
class Solution {
public:
int maxSumTwoNoOverlap(vector<int>& nums, int firstLen, int secondLen) {
return max(helper(nums, firstLen, secondLen),
helper(nums, secondLen, firstLen));
}
private:
int helper(vector<int>& nums, int l, int r) {
const int n = nums.size();
vector<int> left(n);
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i];
if (i >= l)
sum -= nums[i - l];
if (i >= l - 1)
left[i] = i > 0 ? max(left[i - 1], sum) : sum;
}
vector<int> right(n);
sum = 0;
for (int i = n - 1; i >= 0; --i) {
sum += nums[i];
if (i <= n - r - 1)
sum -= nums[i + r];
if (i <= n - r)
right[i] = i < n - 1 ? max(right[i + 1], sum) : sum;
}
int ans = 0;
for (int i = 0; i < n - 1; ++i)
ans = max(ans, left[i] + right[i + 1]);
return ans;
}
}; /* code provided by PROGIEZ */
1031. Maximum Sum of Two Non-Overlapping Subarrays LeetCode Solution in Java
class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
return Math.max(helper(nums, firstLen, secondLen), helper(nums, secondLen, firstLen));
}
private int helper(int[] nums, int l, int r) {
final int n = nums.length;
int[] left = new int[n];
int sum = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i];
if (i >= l)
sum -= nums[i - l];
if (i >= l - 1)
left[i] = i > 0 ? Math.max(left[i - 1], sum) : sum;
}
int[] right = new int[n];
sum = 0;
for (int i = n - 1; i >= 0; --i) {
sum += nums[i];
if (i <= n - r - 1)
sum -= nums[i + r];
if (i <= n - r)
right[i] = i < n - 1 ? Math.max(right[i + 1], sum) : sum;
}
int ans = 0;
for (int i = 0; i < n - 1; ++i)
ans = Math.max(ans, left[i] + right[i + 1]);
return ans;
}
} // code provided by PROGIEZ
1031. Maximum Sum of Two Non-Overlapping Subarrays LeetCode Solution in Python
class Solution:
def maxSumTwoNoOverlap(
self,
nums: list[int],
firstLen: int,
secondLen: int,
) -> int:
def helper(l: int, r: int) -> int:
n = len(nums)
left = [0] * n
summ = 0
for i in range(n):
summ += nums[i]
if i >= l:
summ -= nums[i - l]
if i >= l - 1:
left[i] = max(left[i - 1], summ) if i > 0 else summ
right = [0] * n
summ = 0
for i in reversed(range(n)):
summ += nums[i]
if i <= n - r - 1:
summ -= nums[i + r]
if i <= n - r:
right[i] = max(right[i + 1], summ) if i < n - 1 else summ
return max(left[i] + right[i + 1] for i in range(n - 1))
return max(helper(firstLen, secondLen), helper(secondLen, firstLen)) # code by PROGIEZ
