Programa Javascript para consultas para encontrar subarreglos contiguos de suma máxima de longitud dada en una array giratoria

Dada una array arr[] de N enteros y Q consultas de la forma {X, Y} de los siguientes dos tipos:

  • Si X = 1 , gire la array dada a la izquierda en Y posiciones.
  • Si X = 2 , imprima el subarreglo de suma máxima de longitud Y en el estado actual del arreglo.

Ejemplos: 

Entrada: N = 5, arr[] = {1, 2, 3, 4, 5}, Q = 2, Consulta[][] = {{1, 2}, {2, 3}}
Salida:
Consulta 1: 3 4 5 1 2
Consulta 2: 12
Explicación:
Consulta 1: Desplazar array a la izquierda 2 veces: {1, 2, 3, 4, 5} -> {2, 3, 4, 5, 1} -> {3 , 4, 5, 1, 2}
Consulta 2: el subarreglo de suma máxima de longitud 3 es {3, 4, 5} y la suma es 12

Entrada: N = 5, arr[] = {3, 4, 5, 1, 2}, Q = 3, Consulta[][] = {{1, 3}, {1, 1}, {2, 4} }
Salida: 
Consulta 1: 1 2 3 4 5
Consulta 2: 2 3 4 5 1
Consulta 3: 14
Explicación:
Consulta 1: Desplace la array a la izquierda 3 veces: {3, 4, 5, 1, 2} -> { 4, 5, 1, 2, 3} -> {5, 1, 2, 3, 4} -> {1, 2, 3, 4, 5}
Consulta 2: desplazar array a la izquierda 1 vez: {1, 2, 3, 4, 5} -> {2, 3, 4, 5, 1}
Consulta 3: el subarreglo de suma máxima de longitud 4 es {2, 3, 4, 5} y la suma es 14

Enfoque ingenuo: el enfoque más simple es rotar la array desplazando los elementos uno por uno hasta la distancia Y para consultas de tipo 1 y generar la suma de todos los subarreglos de longitud Y e imprimir la suma máxima si la consulta es de tipo 2
Complejidad temporal: O(Q*N*Y)
Espacio auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el algoritmo de malabarismo para la rotación de array y para encontrar la suma máxima de subarreglo de longitud Y , utilice la técnica de ventana deslizante . Siga los pasos a continuación para resolver el problema:

  1. Si X = 1 , gire la array por Y , utilizando el algoritmo de malabarismo .
  2. De lo contrario, si X = 2 , encuentre el subarreglo de suma máxima de longitud Y utilizando la técnica de ventana deslizante.
  3. Imprima la array si la consulta X es 1 .
  4. De lo contrario, imprima el subarreglo de suma máxima de tamaño Y .

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

Javascript

<script>
// javascript program for 
// the above approach    
// Function to calculate the maximum
    // sum of length k
    function MaxSum(arr , n , k) {
        var i, max_sum = 0, sum = 0;
  
        // Calculating the max sum for
        // the first k elements
        for (i = 0; i < k; i++) {
            sum += arr[i];
        }
        max_sum = sum;
  
        // Find subarray with maximum sum
        while (i < n) {
            // Update the sum
            sum = sum - arr[i - k] + arr[i];
            if (max_sum < sum) {
                max_sum = sum;
            }
            i++;
        }
  
        // Return maximum sum
        return max_sum;
    }
  
    // Function to calculate gcd
    // of the two numbers n1 and n2
    function gcd(n1 , n2) {
        // Base Case
        if (n2 == 0) {
            return n1;
        }
  
        // Recursively find the GCD
        else {
            return gcd(n2, n1 % n2);
        }
    }
  
    // Function to rotate the array by Y
    function RotateArr(arr , n , d) {
        // For handling k >= N
        var i = 0, j = 0;
        d = d % n;
  
        // Dividing the array into
        // number of sets
        var no_of_sets = gcd(d, n);
  
        for (i = 0; i < no_of_sets; i++) {
            var temp = arr[i];
            j = i;
  
            // Rotate the array by Y
            while (true) {
                var k = j + d;
  
                if (k >= n)
                    k = k - n;
  
                if (k == i)
                    break;
  
                arr[j] = arr[k];
                j = k;
            }
  
            // Update arr[j]
            arr[j] = temp;
        }
  
        // Return the rotated array
        return arr;
    }
  
    // Function that performs the queries
    // on the given array
    function performQuery(arr , Q , q) {
        var N = arr.length;
  
        // Traverse each query
        for (i = 0; i < q; i++) {
            // If query of type X = 1
            if (Q[i][0] == 1) {
                arr = RotateArr(arr, N, Q[i][1]);
  
                // Print var the array
                for (var t =0 ;t< arr.length;t++) {
                    document.write(arr[t] + " ");
                }
                document.write("<br/>");
            }
  
            // If query of type X = 2
            else {
                document.write(MaxSum(arr, N, Q[i][1]) + "<br/>");
            }
        }
    }
  
    // Driver Code
      
        // Given array arr
        var arr = [ 1, 2, 3, 4, 5 ];
  
        var q = 5;
  
        // Given Queries
        var Q = [ [ 1, 2 ], [ 2, 3 ], [ 1, 3 ], [ 1, 1 ], [ 2, 4 ] ];
  
        // Function Call
        performQuery(arr, Q, q);
  
// This code contributed by aashish1995
</script>
Producción: 

3 4 5 1 2 
12
1 2 3 4 5 
2 3 4 5 1 
14

Complejidad de tiempo: O(Q*N), donde Q es el número de consultas y N es el tamaño de la array dada.
Espacio Auxiliar: O(N)

¡ Consulte el artículo completo sobre Consultas para encontrar subarreglos contiguos de suma máxima de longitud dada en un arreglo giratorio para obtener más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *