Maximum absolute difference between sum of subarrays of size K
Given an array arr[] of size N and an integer K, the task is to find maximum absolute difference between the sum of subarrays of size K.
Examples :
Input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}, K = 3
Output: 6
Explanation::
Sum of subarray (-2, -3, 4) = -1
Sum of subarray (-3, 4, -1) = 0
Sum of subarray (4, -1, -2) = 1
Sum of subarray (-1, -2, 1) = -2
Sum of subarray (-2, 1, 5) = 4
Sum of subarray (1, 5, -3) = 3
So maximum absolute difference between sum of subarray of size 3 is is (4 – (-2)) = 6.
Input: arr [ ] = {2, 5, -1, 7, -3, -1, -2}, K = 4
Output: 12
Brute Force Approach:
- Initialize a variable max_diff to zero.
- Loop through all pairs of starting indices i and j, where i ranges from 0 to N-K and j ranges from i+1 to N-K.
- For each pair of starting indices i and j, compute the sum of the subarray of size K starting at i, and the sum of the subarray of size K starting at j. To do this, we use a loop that adds up the K elements starting at i and j, respectively.
- Compute the absolute difference between the two sums computed in the previous step, and update the max_diff variable if this absolute difference is greater than the current value of max_diff.
- Return the value of max_diff.
Below is the implementation of the above approach :
C++
// C++ program to find the // maximum absolute difference // between the sum of all // subarrays of size K #include <bits/stdc++.h> using namespace std; // Return absolute difference // between sum of all subarrays // of size k int MaxAbsSumOfKsubArray( int arr[], int K, int N) { int max_diff = 0; for ( int i = 0; i <= N-K; i++) { for ( int j = i+1; j <= N-K; j++) { int sum1 = 0, sum2 = 0; for ( int k = 0; k < K; k++) { sum1 += arr[i+k]; sum2 += arr[j+k]; } max_diff = max(max_diff, abs (sum1 - sum2)); } } return max_diff; } // Driver code int main() { int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int K = 3; int N = sizeof (arr) / sizeof (arr[0]); cout << MaxAbsSumOfKsubArray(arr, K, N) << endl; return 0; } |
Java
import java.util.*; public class Main { // Return absolute difference // between sum of all subarrays // of size k static int MaxAbsSumOfKsubArray( int [] arr, int K, int N) { int max_diff = 0 ; for ( int i = 0 ; i <= N - K; i++) { for ( int j = i + 1 ; j <= N - K; j++) { int sum1 = 0 , sum2 = 0 ; for ( int k = 0 ; k < K; k++) { sum1 += arr[i + k]; sum2 += arr[j + k]; } max_diff = Math.max(max_diff, Math.abs(sum1 - sum2)); } } return max_diff; } // Driver code public static void main(String[] args) { int [] arr = { - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 }; int K = 3 ; int N = arr.length; System.out.println(MaxAbsSumOfKsubArray(arr, K, N)); } } // This code is contributed by Prajwal Kandekar |
Python3
def max_abs_sum_of_k_subarray(arr, K, N): # Function to find the maximum absolute difference between the sums of two subarrays of length K max_diff = 0 # Iterate through all possible starting indices of the first subarray for i in range (N - K + 1 ): # Iterate through all possible starting indices of the second subarray for j in range (i + 1 , N - K + 1 ): sum1 = 0 sum2 = 0 # Compute the sum of elements in the first subarray for k in range (K): sum1 + = arr[i + k] # Compute the sum of elements in the second subarray for k in range (K): sum2 + = arr[j + k] # Update the maximum difference if the absolute difference between the sums is greater max_diff = max (max_diff, abs (sum1 - sum2)) return max_diff # Driver code arr = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ] K = 3 N = len (arr) print (max_abs_sum_of_k_subarray(arr, K, N)) |
C#
// C# program to find the // maximum absolute difference // between the sum of all // subarrays of size K using System; public static class GFG { // Return absolute difference // between sum of all subarrays // of size k static int MaxAbsSumOfKsubArray( int [] arr, int K, int N) { int max_diff = 0; for ( int i = 0; i <= N - K; i++) { for ( int j = i + 1; j <= N - K; j++) { int sum1 = 0, sum2 = 0; for ( int k = 0; k < K; k++) { sum1 += arr[i + k]; sum2 += arr[j + k]; } max_diff = Math.Max(max_diff, Math.Abs(sum1 - sum2)); } } return max_diff; } // Driver code public static void Main() { int [] arr = { -2, -3, 4, -1, -2, 1, 5, -3 }; int K = 3; int N = arr.Length; Console.WriteLine(MaxAbsSumOfKsubArray(arr, K, N)); } } // This code is contributed by Utkarsh Kumar |
Javascript
// Javascript program // Return absolute difference // between sum of all subarrays // of size k function maxAbsSumOfKsubArray(arr, K, N) { let maxDiff = 0; for (let i = 0; i <= N - K; i++) { for (let j = i + 1; j <= N - K; j++) { let sum1 = 0, sum2 = 0; for (let k = 0; k < K; k++) { sum1 += arr[i + k]; sum2 += arr[j + k]; } maxDiff = Math.max(maxDiff, Math.abs(sum1 - sum2)); } } return maxDiff; } // Driver code const arr = [-2, -3, 4, -1, -2, 1, 5, -3]; const K = 3; const N = arr.length; console.log(maxAbsSumOfKsubArray(arr, K, N)); |
6
Time Complexity: O(N^3)
Auxiliary Space: O(1)
Efficient Approach
The idea is to use Sliding Window Technique. Follow the steps below to solve the problem:
- Check if K is greater than N then return -1.
-
- maxSum : Store maximum sum of K size subarray.
- minSum : Store minimum sum of K size subarray.
- sum : Store current sum of K size subarray.
- start : Remove left most element which is no longer part of K size subarray.
- Calculate the sum of first K size subarray and update maxSum and minSum, decrement sum by arr[start] and increment start by 1.
- Traverse arr from K to N and do the following operations:
- Increment sum by arr[i].
- Update maxSum and minSum.
- Decrement sum by arr[start].
- Increment start by 1.
- Return absolute difference between maxSum and minSum.
Below is the implementation of the above approach :
C++
// C++ program to find the // maximum absolute difference // between the sum of all // subarrays of size K #include <bits/stdc++.h> using namespace std; // Return absolute difference // between sum of all subarrays // of size k int MaxAbsSumOfKsubArray( int arr[], int K, int N) { // Stores maximum sum of // all K size subarrays int maxSum = INT_MIN; // Stores minimum sum of // all K size subarray int minSum = INT_MAX; // Stores the sum of current // subarray of size K int sum = 0; // Starting index of the // current subarray int start = 0; int i = 0; if (N < K) return -1; // Calculate the sum of // first K elements while (i < K) { sum += arr[i]; i++; } // Update maxSum and minSum maxSum = max(maxSum, sum); minSum = min(minSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; // Traverse arr for the // remaining subarrays while (i < N) { // Increment sum by arr[i] sum += arr[i]; // Increment i i++; // Update maxSum and minSum maxSum = max(maxSum, sum); minSum = min(minSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; } // Return absolute difference // between maxSum and minSum return abs (maxSum - minSum); } // Driver code int main() { int arr[] = { -2, -3, 4, -1, -2, 1, 5, -3 }; int K = 3; int N = sizeof (arr) / sizeof (arr[0]); cout << MaxAbsSumOfKsubArray(arr, K, N) << endl; return 0; } // This code is contributed by divyeshrabadiya07 |
Java
// Java program to find the // maximum absolute difference // between the sum of all // subarrays of size K import java.util.*; class GFG { // Return absolute difference // between sum of all subarrays // of size k static int MaxAbsSumOfKsubArray( int [] arr, int K, int N) { // Stores maximum sum of // all K size subarrays int maxSum = Integer.MIN_VALUE; // Stores minimum sum of // all K size subarray int minSum = Integer.MAX_VALUE; // Stores the sum of current // subarray of size K int sum = 0 ; // Starting index of the // current subarray int start = 0 ; int i = 0 ; if (N < K) return - 1 ; // Calculate the sum of // first K elements while (i < K) { sum += arr[i]; i++; } // Update maxSum and minSum maxSum = Math.max(maxSum, sum); minSum = Math.min(minSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; // Traverse arr for the // remaining subarrays while (i < N) { // Increment sum by arr[i] sum += arr[i]; // Increment i i++; // Update maxSum and minSum maxSum = Math.max(maxSum, sum); minSum = Math.min(minSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; } // Return absolute difference // between maxSum and minSum return Math.abs(maxSum - minSum); } // Driver code public static void main(String[] args) { int [] arr = { - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 }; int K = 3 ; int N = arr.length; System.out.println( MaxAbsSumOfKsubArray( arr, K, N)); } } |
Python3
# Python3 program to find the # maximum absolute difference # between the sum of all # subarrays of size K import sys # Return absolute difference # between sum of all subarrays # of size k def MaxAbsSumOfKsubArray(arr, K, N): # Stores maximum sum of # all K size subarrays maxSum = - sys.maxsize - 1 # Stores minimum sum of # all K size subarray minSum = sys.maxsize # Stores the sum of current # subarray of size K sum = 0 # Starting index of the # current subarray start = 0 i = 0 if (N < K): return - 1 # Calculate the sum of # first K elements while (i < K): sum + = arr[i] i + = 1 # Update maxSum and minSum maxSum = max (maxSum, sum ) minSum = min (minSum, sum ) # Decrement sum by arr[start] # and increment start by 1 sum - = arr[start] start + = 1 # Traverse arr for the # remaining subarrays while (i < N): # Increment sum by arr[i] sum + = arr[i] # Increment i i + = 1 # Update maxSum and minSum maxSum = max (maxSum, sum ) minSum = min (minSum, sum ) # Decrement sum by arr[start] # and increment start by 1 sum - = arr[start] start + = 1 # Return absolute difference # between maxSum and minSum return abs (maxSum - minSum) # Driver code arr = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ] K = 3 N = len (arr) print (MaxAbsSumOfKsubArray(arr, K, N)) # This code is contributed by sanjoy_62 |
C#
// C# program to find the // maximum absolute difference // between the sum of all // subarrays of size K using System; class GFG{ // Return absolute difference // between sum of all subarrays // of size k static int MaxAbsSumOfKsubArray( int [] arr, int K, int N) { // Stores maximum sum of // all K size subarrays int MaxSum = Int32.MinValue; // Stores minimum sum of // all K size subarray int MinSum = Int32.MaxValue; // Stores the sum of current // subarray of size K int sum = 0; // Starting index of the // current subarray int start = 0; int i = 0; if (N < K) return -1; // Calculate the sum of // first K elements while (i < K) { sum += arr[i]; i++; } // Update maxSum and minSum MaxSum = Math.Max(MaxSum, sum); MinSum = Math.Min(MinSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; // Traverse arr for the // remaining subarrays while (i < N) { // Increment sum by arr[i] sum += arr[i]; // Increment i i++; // Update maxSum and minSum MaxSum = Math.Max(MaxSum, sum); MinSum = Math.Min(MinSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; } // Return absolute difference // between maxSum and minSum return Math.Abs(MaxSum - MinSum); } // Driver code public static void Main(String[] args) { int [] arr = { -2, -3, 4, -1, -2, 1, 5, -3 }; int K = 3; int N = arr.Length; Console.Write(MaxAbsSumOfKsubArray(arr, K, N)); } } // This code is contributed // by shivanisinghss2110 |
Javascript
<script> // Javascript program to find the // maximum absolute difference // between the sum of all // subarrays of size K // Return absolute difference // between sum of all subarrays // of size k function MaxAbsSumOfKsubArray(arr, K, N) { // Stores maximum sum of // all K size subarrays let maxSum = Number.MIN_VALUE; // Stores minimum sum of // all K size subarray let minSum = Number.MAX_VALUE; // Stores the sum of current // subarray of size K let sum = 0; // Starting index of the // current subarray let start = 0; let i = 0; if (N < K) return -1; // Calculate the sum of // first K elements while (i < K) { sum += arr[i]; i++; } // Update maxSum and minSum maxSum = Math.max(maxSum, sum); minSum = Math.min(minSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; // Traverse arr for the // remaining subarrays while (i < N) { // Increment sum by arr[i] sum += arr[i]; // Increment i i++; // Update maxSum and minSum maxSum = Math.max(maxSum, sum); minSum = Math.min(minSum, sum); // Decrement sum by arr[start] // and increment start by 1 sum -= arr[start++]; } // Return absolute difference // between maxSum and minSum return Math.abs(maxSum - minSum); } let arr = [ -2, -3, 4, -1, -2, 1, 5, -3 ]; let K = 3; let N = arr.length; document.write(MaxAbsSumOfKsubArray(arr, K, N)); </script> |
6
Time Complexity: O (N)
Auxiliary Space: O (1)
Contact Us