Longitud máxima de subarreglo con la misma suma en los índices correspondientes de dos Arreglos

Dados dos arreglos A[] y B[], ambos compuestos por N enteros, la tarea es encontrar la longitud máxima del subarreglo [i, j] tal que la suma de A[i… j] sea igual a B[i… j ] .

Ejemplos:

Entrada: A[] = {1, 1, 0, 1}, B[] = {0, 1, 1, 0}
Salida: 3
Explicación: Para (i, j) = (0, 2), suma de A [0… 2] = suma de B[0… 2] (es decir, A[0]+A[1]+A[2] = B[0]+B[1]+B[2] => 1+ 1+0 = 0+1+1 => 2 = 2). De manera similar, para (i, j) = (1, 3), suma de A[1… 3] = B[1… 3]. Por lo tanto, la longitud del subarreglo con igual suma es 3, que es el máximo posible.

Entrada: A[] = {1, 2, 3, 4}, B[] = {4, 3, 2, 1}
Salida: 4

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso con la ayuda de mapas desordenados . Se puede observar que para un par (i, j) , si la suma de A[i… j] = suma de B[i… j] , entonces $\sum_{x=i}^{j} (A[x] - B[x]) = 0$ debe ser cierto. Por lo tanto, se puede crear una array de suma de prefijos de la diferencia (A[x] – B[x]) . Se puede observar que los valores repetidos en la array de suma de prefijos representan que la suma de un subarreglo entre los dos valores repetidos debe ser 0. Por lo tanto, mantenga un registro del tamaño máximo de tales subarreglos en una variable maxSize que será el requerido responder.

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

C++

// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
 
// Function to find maximum length of subarray
// of array A and B having equal sum
int maxLength(vector<int>& A, vector<int>& B)
{
    int n = A.size();
 
    // Stores the maximum size of valid subarray
    int maxSize = 0;
 
    // Stores the prefix sum of the difference
    // of the given arrays
    unordered_map<int, int> pre;
    int diff = 0;
    pre[0] = 0;
 
    // Traverse the given array
    for (int i = 0; i < n; i++) {
 
        // Add the difference of the
        // corresponding array element
        diff += (A[i] - B[i]);
 
        // If current difference is not present
        if (pre.find(diff) == pre.end()) {
            pre = i + 1;
        }
 
        // If current difference is present,
        // update the value of maxSize
        else {
            maxSize = max(maxSize, i - pre + 1);
        }
    }
 
    // Return the maximum length
    return maxSize;
}
 
// Driver Code
int main()
{
    vector<int> A = { 1, 2, 3, 4 };
    vector<int> B = { 4, 3, 2, 1 };
 
    cout << maxLength(A, B);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.HashMap;
class GFG {
 
    // Function to find maximum length of subarray
    // of array A and B having equal sum
    public static int maxLength(int[] A, int[] B) {
        int n = A.length;
 
        // Stores the maximum size of valid subarray
        int maxSize = 0;
 
        // Stores the prefix sum of the difference
        // of the given arrays
        HashMap<Integer, Integer> pre = new HashMap<Integer, Integer>();
        int diff = 0;
        pre.put(0, 0);
 
        // Traverse the given array
        for (int i = 0; i < n; i++) {
 
            // Add the difference of the
            // corresponding array element
            diff += (A[i] - B[i]);
 
            // If current difference is not present
            if (!pre.containsKey(diff)) {
                pre.put(diff, i + 1);
            }
 
            // If current difference is present,
            // update the value of maxSize
            else {
                maxSize = Math.max(maxSize, i - pre.get(diff));
            }
        }
 
        // Return the maximum length
        return maxSize;
    }
 
    // Driver Code
    public static void main(String args[]) {
        int[] A = { 1, 2, 3, 4 };
        int[] B = { 4, 3, 2, 1 };
 
        System.out.println(maxLength(A, B));
 
    }
}
 
// This code is contributed by gfgking.

Python3

# python program for the above approach
 
# Function to find maximum length of subarray
# of array A and B having equal sum
 
 
def maxLength(A,  B):
 
    n = len(A)
 
    # Stores the maximum size of valid subarray
    maxSize = 0
 
    # Stores the prefix sum of the difference
    # of the given arrays
    pre = {}
    diff = 0
    pre[0] = 0
 
    # Traverse the given array
    for i in range(0, n):
 
        # Add the difference of the
        # corresponding array element
        diff += (A[i] - B[i])
 
        # If current difference is not present
        if (not (diff in pre)):
            pre = i + 1
 
        # If current difference is present,
        # update the value of maxSize
        else:
            maxSize = max(maxSize, i - pre + 1)
 
    # Return the maximum length
    return maxSize
 
 
# Driver Code
if __name__ == "__main__":
 
    A = [1, 2, 3, 4]
    B = [4, 3, 2, 1]
 
    print(maxLength(A, B))
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
    // Function to find maximum length of subarray
    // of array A and B having equal sum
    public static int maxLength(int[] A, int[] B) {
        int n = A.Length;
 
        // Stores the maximum size of valid subarray
        int maxSize = 0;
 
        // Stores the prefix sum of the difference
        // of the given arrays
        Dictionary<int, int> pre =
                new Dictionary<int, int>();
                 
        int diff = 0;
        pre.Add(0, 0);
 
        // Traverse the given array
        for (int i = 0; i < n; i++) {
 
            // Add the difference of the
            // corresponding array element
            diff += (A[i] - B[i]);
 
            // If current difference is not present
            if (!pre.ContainsKey(diff)) {
                pre.Add(diff, i + 1);
            }
 
            // If current difference is present,
            // update the value of maxSize
            else {
                maxSize = Math.Max(maxSize, i - pre[(diff)]);
            }
        }
 
        // Return the maximum length
        return maxSize;
    }
 
// Driver Code
public static void Main()
{
    int[] A = { 1, 2, 3, 4 };
    int[] B = { 4, 3, 2, 1 };
 
    Console.Write(maxLength(A, B));
}
}
 
// This code is contributed by sanjoy_62.

Javascript

<script>
    // JavaScript program for the above approach
 
 
    // Function to find maximum length of subarray
    // of array A and B having equal sum
    const maxLength = (A, B) => {
        let n = A.length;
 
        // Stores the maximum size of valid subarray
        let maxSize = 0;
 
        // Stores the prefix sum of the difference
        // of the given arrays
        let pre = {};
        let diff = 0;
        pre[0] = 0;
 
        // Traverse the given array
        for (let i = 0; i < n; i++) {
 
            // Add the difference of the
            // corresponding array element
            diff += (A[i] - B[i]);
 
            // If current difference is not present
 
            if (!(diff in pre)) {
                pre = i + 1;
            }
 
            // If current difference is present,
            // update the value of maxSize
            else {
                maxSize = Math.max(maxSize, i - pre + 1);
            }
        }
 
        // Return the maximum length
        return maxSize;
    }
 
    // Driver Code
 
    let A = [1, 2, 3, 4];
    let B = [4, 3, 2, 1];
 
    document.write(maxLength(A, B));
 
// This code is contributed by rakeshsahni.
</script>

Producción

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

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

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta