Máxima diferencia absoluta entre la suma de subarreglos de tamaño K

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar la máxima diferencia absoluta entre la suma de subarreglos de tamaño K.
Ejemplos: 
 

Entrada: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}, K = 3 
Salida: 6 
Explicación : 
Suma de subarreglo (-2, -3, 4) = -1 
Suma del subarreglo (-3, 4, -1) = 0 
Suma del subarreglo (4, -1, -2) = 1 
Suma del subarreglo (-1, -2, 1) = -2 
Suma del subarreglo ( -2, 1, 5) = 4 
Suma del subarreglo (1, 5, -3) = 3 
Entonces, la máxima diferencia absoluta entre la suma del subarreglo de tamaño 3 es (4 – (-2)) = 6.
Entrada: arr [ ] = {2, 5, -1, 7, -3, -1, -2}, K = 4 
Salida: 12 
 

Enfoque ingenuo 
El enfoque más simple es generar todos los subarreglos de tamaño K y encontrar la suma mínima y la suma máxima entre ellos. Finalmente, devuelva la diferencia absoluta entre las sumas máxima y mínima. 
Tiempo Complejidad: O( N 2 )  
Espacio Auxiliar: O (1)
Enfoque Eficiente 
La idea es utilizar la Técnica de Ventana Deslizante . Siga los pasos a continuación para resolver el problema:
 

  1. Compruebe si K es mayor que N y luego devuelva -1.
  2.  
    • maxSum : almacena la suma máxima del subarreglo de tamaño K.
    • minSum : almacena la suma mínima del subarreglo de tamaño K.
    • sum : almacena la suma actual del subarreglo de tamaño K.
    • start : elimine el elemento más a la izquierda que ya no forma parte del subarreglo de tamaño K.
  3. Calcule la suma del primer subarreglo de tamaño K y actualice maxSum y minSum , disminuya la suma en arr[start] e incremente start en 1.
  4. Recorra arr de K a N y realice las siguientes operaciones: 
    • Incrementar suma por arr[i] .
    • Actualice maxSum y minSum .
    • Decrementar suma por arr[inicio] .
    • Incremento de inicio en 1.
  5. Devuelve la diferencia absoluta entre maxSum y minSum .

A continuación se muestra la implementación del enfoque anterior:
 

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>
Producción: 

6

 

Complejidad Temporal: O (N)  
Espacio Auxiliar: O (1)
 

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *