Data Modelling & AI Data Structure & Algorithm

Maximum absolute difference between sum of subarrays of size K

23 June 2025

0

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));

Output

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>

Output

Time Complexity: O (N)
Auxiliary Space: O (1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Maximum absolute difference between sum of subarrays of size K

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

From Word2Vec to LLM2Vec: How to Choose the Right Embedding Model for RAG

How to Debug Slow Search Requests in Milvus

When Context Engineering Is Done Right, Hallucinations Can Be the Spark of AI Creativity

LEAVE A REPLY Cancel reply

Most Popular

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

Uh-oh, Pixel 10 users are still getting “fuzzy display” bug after Google’s fix

EDITOR PICKS

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

POPULAR POSTS

I used the Google Pixel 10 Pro Fold and Galaxy Z Fold 7, and I’ve never been more conflicted

I wasn’t looking for a new app — but this one completely changed how I see daylight

It’s not sleek, it’s not cheap — but the Pixel 10 Pro Fold won me over anyway

POPULAR CATEGORY

ABOUT US

FOLLOW US