CSES Solutions - Maximum Subarray Sum II

Given an array arr[] of N integers, your task is to find the maximum sum of values in a contiguous subarray with length between A and B.

Examples:

Input: N = 8, A = 1, B = 2, arr[] = {-1, 3, -2, 5, 3, -5, 2, 2}
Output: 8
Explanation: The subarray with maximum sum is {5, 3}, the length between 1 and 2, and the sum is 8.

Input: N = 8, A = 1, B = 1, arr[] = {-1, 3, -2, 5, 3, -5, 2, 2}
Output: 5
Explanation: The subarray with maximum sum is {5} with length between 1 and 1, and the sum is 5.

Approach: To solve the problem, follow the below idea:

The idea is to calculate the prefix sum of the given array and calculate the maximum subarray sum, with length being between a and b for each subarray starting at index i. To calculate the maximum subarray sum starting at index i, will be: max(prefixSum[i+a-1] ....... prefixSum[i+b-1]) - prefixSum[i-1], i.e., we need to pick the maximum value from the prefixSum array from the index (i+a-1) to (i+b-1) and subtract prefixSum[i-1] from it, this gives the maximum subarray starting from index i and the length being between a and b. The final answer will be the maximum value among all possible starting index i from 1 to (n-a).

To find the maximum value in the range for each starting index i, it can be observed that window size will be constant which is (b-a+1). So, we can use a deque to maintain the maximum value for each window. You can refer to this article for more details: Sliding Window Maximum (Maximum of all subarrays of size K)

Step-by-step algorithm:

• Initialize a prefixSum[] array of size n+1 to store the cumulative sum of the given array and Initialize a deque (dq) to store the indices of elements in a increasing order of their values.
• Loop through the first (b-1) indices and maintain the deque such that it always contains indices of elements in increasing order of their prefix sum values.
• Loop through each starting index i from 0 to (n-a), for finding the maximum subarray sum starting at index (i+1).
  • Inside the loop, adjust the deque to maintain the maximum value for the current window of size (b-a+1).
  • If the current window's right end has a prefix sum greater than the front element in the deque, pop elements from the front until this condition is satisfied, and then push the right end index to the front.
  • If the index of maximum element outside the current window , pop elements from the back of the deque until the back index is within the current window.
• Update the answer by taking the maximum of the current answer and the difference between the prefix sum at the back of the deque and the prefix sum at index I.
• After the loop, print the final answer, which represents the maximum sum of values in a contiguous subarray with length between a and b.

Below is the implementation of above approach:

#include <bits/stdc++.h> using namespace std; typedef long long ll; void MaximumSubarraySumII(int N, int A, int B,  vector<ll>& arr) {  // Initialize a deque to store indices in increasing  // order of prefix sum values  deque<ll> dq;  // Initialize a prefixSum array to store cumulative sums  vector<ll> prefixSum(N + 1);  // Initialize the answer to track the maximum sum  ll ans = LLONG_MIN;  // Calculate cumulative sums  for (int i = 1; i <= N; i++) {  prefixSum[i] += prefixSum[i - 1] + arr[i - 1];  }  // Loop through the first (B-1) indices to initialize  // deque  for (int i = 1; i < B; i++) {  // Maintain deque in increasing order of prefix sum  // values  while (!dq.empty()  && prefixSum[dq.front()] <= prefixSum[i]) {  dq.pop_front();  }  dq.push_front(i);  }  // Loop through each starting index i from 0 to (n-a)  for (int i = 0; i <= (N - A); i++) {  // Maintain deque in increasing order of prefix sum  // values  while (i + B <= N && !dq.empty()  && prefixSum[dq.front()]  <= prefixSum[i + B]) {  dq.pop_front();  }  // Push the right end index to the front of deque  if (i + B <= N)  dq.push_front(i + B);  // If the index of maximum element outside the  // current window , pop elements from the back of  // the deque until the back index(index of maximum  // element) is within the current window.  while (!dq.empty() && dq.back() < (A + i)) {  dq.pop_back();  }  // Update the answer by taking the maximum of the  // current answer and the difference between the  // prefix sum at the back(maximum element) of the  // deque and the prefix sum at index i    ans = max(ans, prefixSum[dq.back()] - prefixSum[i]);  }  // Print the final answer  cout << ans << "\n"; } // Driver Code int main() {  // Read input values n, a, b, and the array arr from the  // standard input  int N = 8, A = 1, B = 2;  vector<ll> arr = { -1, 3, -2, 5, 3, -5, 2, 2 };  // Invoke the function MaximumSubarraySumII with the  // provided inputs  MaximumSubarraySumII(N, A, B, arr); } 

import java.util.ArrayDeque; import java.util.Deque; public class MaximumSubarraySumII {  static void maximumSubarraySumII(int N, int A, int B, long[] arr) {  // Initialize a deque to store indices in increasing  // order of prefix sum values  Deque<Integer> dq = new ArrayDeque<>();  // Initialize a prefixSum array to store cumulative sums  long[] prefixSum = new long[N + 1];  // Initialize the answer to track the maximum sum  long ans = Long.MIN_VALUE;  // Calculate cumulative sums  for (int i = 1; i <= N; i++) {  prefixSum[i] += prefixSum[i - 1] + arr[i - 1];  }  // Loop through the first (B-1) indices to initialize deque  for (int i = 1; i < B; i++) {  // Maintain deque in increasing order of prefix sum values  while (!dq.isEmpty() && prefixSum[dq.peekFirst()] <= prefixSum[i]) {  dq.pollFirst();  }  dq.addFirst(i);  }  // Loop through each starting index i from 0 to (N - A)  for (int i = 0; i <= (N - A); i++) {  // Maintain deque in increasing order of prefix sum values  while (i + B <= N && !dq.isEmpty() && prefixSum[dq.peekFirst()] <= prefixSum[i + B]) {  dq.pollFirst();  }  // Push the right end index to the front of deque  if (i + B <= N)  dq.addFirst(i + B);  // If the index of maximum element outside the  // current window, pop elements from the back of  // the deque until the back index (index of maximum  // element) is within the current window.  while (!dq.isEmpty() && dq.peekLast() < (A + i)) {  dq.pollLast();  }  // Update the answer by taking the maximum of the  // current answer and the difference between the  // prefix sum at the back (maximum element) of the  // deque and the prefix sum at index i  ans = Math.max(ans, prefixSum[dq.peekLast()] - prefixSum[i]);  }  // Print the final answer  System.out.println(ans);  }  // Driver Code  public static void main(String[] args) {  // Read input values N, A, B, and the array arr from the standard input  int N = 8, A = 1, B = 2;  long[] arr = { -1, 3, -2, 5, 3, -5, 2, 2 };  // Invoke the function maximumSubarraySumII with the provided inputs  maximumSubarraySumII(N, A, B, arr);  } } // This code is contributed by rambabuguphka 

using System; using System.Collections.Generic; public class Program {  public static void MaximumSubarraySumII(int N, int A, int B, List<long> arr)  {  // Initialize a deque to store indices in increasing order of prefix sum values  LinkedList<long> dq = new LinkedList<long>();  // Initialize a prefixSum array to store cumulative sums  List<long> prefixSum = new List<long>(new long[N + 1]);  // Initialize the answer to track the maximum sum  long ans = long.MinValue;  // Calculate cumulative sums  for (int i = 1; i <= N; i++)  {  prefixSum[i] += prefixSum[i - 1] + arr[i - 1];  }  // Loop through the first (B-1) indices to initialize deque  for (int i = 1; i < B; i++)  {  // Maintain deque in increasing order of prefix sum values  while (dq.Count > 0 && prefixSum[(int)dq.First.Value] <= prefixSum[i])  {  dq.RemoveFirst();  }  dq.AddFirst(i);  }  // Loop through each starting index i from 0 to (n-a)  for (int i = 0; i <= (N - A); i++)  {  // Maintain deque in increasing order of prefix sum values  while (i + B <= N && dq.Count > 0 && prefixSum[(int)dq.First.Value] <= prefixSum[i + B])  {  dq.RemoveFirst();  }  // Push the right end index to the front of deque  if (i + B <= N)  dq.AddFirst(i + B);  // If the index of maximum element outside the current window, pop elements from the back of the deque until the back index(index of maximum element) is within the current window.  while (dq.Count > 0 && dq.Last.Value < (A + i))  {  dq.RemoveLast();  }  // Update the answer by taking the maximum of the current answer and the difference between the prefix sum at the back(maximum element) of the deque and the prefix sum at index i  ans = Math.Max(ans, prefixSum[(int)dq.Last.Value] - prefixSum[i]);  }  // Print the final answer  Console.WriteLine(ans);  }  public static void Main()  {  // Read input values n, a, b, and the array arr from the standard input  int N = 8, A = 1, B = 2;  List<long> arr = new List<long> { -1, 3, -2, 5, 3, -5, 2, 2 };  // Invoke the function MaximumSubarraySumII with the provided inputs  MaximumSubarraySumII(N, A, B, arr);  } } 

function maximumSubarraySumII(N, A, B, arr) {  // Initialize a deque to store indices in increasing  // order of prefix sum values  let dq = [];  // Initialize a prefixSum array to store cumulative sums  let prefixSum = new Array(N + 1).fill(0);  // Initialize the answer to track the maximum sum  let ans = Number.MIN_SAFE_INTEGER;  // Calculate cumulative sums  for (let i = 1; i <= N; i++) {  prefixSum[i] += prefixSum[i - 1] + arr[i - 1];  }  // Loop through the first (B-1) indices to initialize  // deque  for (let i = 1; i < B; i++) {  // Maintain deque in increasing order of prefix sum  // values  while (dq.length !== 0 && prefixSum[dq[0]] <= prefixSum[i]) {  dq.shift();  }  dq.unshift(i);  }  // Loop through each starting index i from 0 to (n-a)  for (let i = 0; i <= (N - A); i++) {  // Maintain deque in increasing order of prefix sum  // values  while (i + B <= N && dq.length !== 0 && prefixSum[dq[0]] <= prefixSum[i + B]) {  dq.shift();  }  // Push the right end index to the front of deque  if (i + B <= N)  dq.unshift(i + B);  // If the index of maximum element outside the  // current window , pop elements from the back of  // the deque until the back index(index of maximum  // element) is within the current window.  while (dq.length !== 0 && dq[dq.length - 1] < (A + i)) {  dq.pop();  }  // Update the answer by taking the maximum of the  // current answer and the difference between the  // prefix sum at the back(maximum element) of the  // deque and the prefix sum at index i  ans = Math.max(ans, prefixSum[dq[dq.length - 1]] - prefixSum[i]);  }  // Print the final answer  console.log(ans); } // Driver Code // Read input values n, a, b, and the array arr from the // standard input let N = 8, A = 1, B = 2; let arr = [-1, 3, -2, 5, 3, -5, 2, 2]; // Invoke the function MaximumSubarraySumII with the // provided inputs maximumSubarraySumII(N, A, B, arr); 

from collections import deque def MaximumSubarraySumII(N, A, B, arr): # Initialize a deque to store indices in increasing # order of prefix sum values dq = deque() # Initialize a prefixSum array to store cumulative sums prefix_sum = [0] * (N + 1) # Initialize the answer to track the maximum sum ans = float('-inf') # Calculate cumulative sums for i in range(1, N + 1): prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1] # Loop through the first (B-1) indices to initialize # deque for i in range(1, B): # Maintain deque in increasing order of prefix sum # values while dq and prefix_sum[dq[0]] <= prefix_sum[i]: dq.popleft() dq.appendleft(i) # Loop through each starting index i from 0 to (n-a) for i in range(N - A + 1): # Maintain deque in increasing order of prefix sum # values while i + B <= N and dq and prefix_sum[dq[0]] <= prefix_sum[i + B]: dq.popleft() # Push the right end index to the front of deque if i + B <= N: dq.appendleft(i + B) # If the index of maximum element outside the # current window, pop elements from the back of # the deque until the back index(index of maximum # element) is within the current window. while dq and dq[-1] < A + i: dq.pop() # Update the answer by taking the maximum of the # current answer and the difference between the # prefix sum at the back(maximum element) of the # deque and the prefix sum at index i ans = max(ans, prefix_sum[dq[-1]] - prefix_sum[i]) # Print the final answer print(ans) # Driver Code if __name__ == "__main__": # Provided input values N = 8 A = 1 B = 2 arr = [-1, 3, -2, 5, 3, -5, 2, 2] # Invoke the function maximum_subarray_sum_ii with the # provided inputs MaximumSubarraySumII(N, A, B, arr) 

8

Time Complexity: O(N), where N is the size of input array arr[].
Auxiliary Space: O(N)