29. Maximum Subarray Sum 2
✅ GFG solution to the Maximum Subarray Sum with Length Constraints problem: find maximum sum of subarray with length between a and b using monotonic deque optimization. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given an array arr[] of integers and two integers a and b. Your task is to find the maximum possible sum of a contiguous subarray whose length is at least a and at most b.
A subarray is a contiguous sequence of elements within an array. The goal is to efficiently find the maximum sum among all valid subarrays satisfying the length constraints.
📘 Examples
Example 1
Input: arr[] = [4, 5, -1, -2, 6], a = 2, b = 4
Output: 9
Explanation: The subarray [4, 5] has length 2 and sum 9, which is the maximum among
all subarrays of length between 2 and 4.Example 2
Input: arr[] = [-1, 3, -1, -2, 5, 3, -5, 2, 2], a = 3, b = 5
Output: 8
Explanation: The subarray [3, -1, -2, 5, 3] has length 5 and sum 8, which is the
maximum among all subarrays of length between 3 and 5.🔒 Constraints
$1 \le \text{arr.size()} \le 10^5$
$-10^5 \le \text{arr}[i] \le 10^5$
$1 \le a \le b \le \text{arr.size()}$
✅ My Approach
The optimal approach uses Prefix Sum combined with a Monotonic Deque to efficiently track the minimum prefix sum in a sliding window:
Monotonic Deque with Prefix Sum
Compute Prefix Sums:
Build a prefix sum array where
pre[i]represents the sum of elements from index 0 to i-1.This allows O(1) calculation of any subarray sum as
pre[j] - pre[i].
Initialize Deque:
Use a deque to maintain indices of prefix sums in increasing order.
The deque helps find the minimum prefix sum in the valid window efficiently.
Iterate Through Ending Positions:
For each position
ifromaton, consider it as the ending position of a subarray.Calculate valid starting position range:
[max(0, i-b), i-a].
Maintain Monotonic Property:
Remove indices from deque back if their prefix values are greater than or equal to current prefix.
This ensures deque maintains increasing order of prefix values.
Add current valid starting position to deque.
Remove Invalid Indices:
Remove indices from deque front if they fall outside the valid window range.
The front of deque always contains the minimum prefix in valid range.
Calculate Maximum Sum:
Compute subarray sum as
pre[i] - pre[dq.front()]wheredq.front()gives minimum prefix in valid window.Update result with maximum sum found.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), as each element is added to and removed from the deque at most once, resulting in amortized constant time operations per element. The prefix sum computation also takes O(n) time.
Expected Auxiliary Space Complexity: O(n), as we use additional space for the prefix sum array of size n+1 and a deque that can hold at most n elements in the worst case.
🧑💻 Code (C++)
class Solution {
public:
int maxSubarrSum(vector<int>& arr, int a, int b) {
int n = arr.size(), res = INT_MIN;
vector<int> pre(n + 1);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + arr[i];
deque<int> dq;
for (int i = a; i <= n; i++) {
int l = max(0, i - b), r = i - a;
while (!dq.empty() && pre[dq.back()] >= pre[r]) dq.pop_back();
dq.push_back(r);
while (!dq.empty() && dq.front() < l) dq.pop_front();
res = max(res, pre[i] - pre[dq.front()]);
}
return res;
}
};☕ Code (Java)
class Solution {
public int maxSubarrSum(int[] arr, int a, int b) {
int n = arr.length, res = Integer.MIN_VALUE;
int[] pre = new int[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + arr[i];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = a; i <= n; i++) {
int l = Math.max(0, i - b), r = i - a;
while (!dq.isEmpty() && pre[dq.peekLast()] >= pre[r]) dq.pollLast();
dq.offerLast(r);
while (!dq.isEmpty() && dq.peekFirst() < l) dq.pollFirst();
res = Math.max(res, pre[i] - pre[dq.peekFirst()]);
}
return res;
}
}🐍 Code (Python)
class Solution:
def maxSubarrSum(self, arr, a, b):
n, res = len(arr), float('-inf')
pre = [0] * (n + 1)
for i in range(n): pre[i + 1] = pre[i] + arr[i]
dq = []
for i in range(a, n + 1):
l, r = max(0, i - b), i - a
while dq and pre[dq[-1]] >= pre[r]: dq.pop()
dq.append(r)
while dq and dq[0] < l: dq.pop(0)
res = max(res, pre[i] - pre[dq[0]])
return res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated