Programa Python3 para consultas para encontrar la suma máxima de subarreglos contiguos 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:

Python3

# Python3 program for the above approach
  
# Function to calculate the maximum
# sum of length k
def MaxSum(arr, n, k):
      
    i, max_sum = 0, 0
    sum = 0
  
    # Calculating the max sum for
    # the first k elements
    while i < k:
        sum += arr[i]
        i += 1
          
    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 += 1
  
    # Return maximum sum
    return max_sum
  
# Function to calculate gcd of the
# two numbers n1 and n2
def 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
def RotateArr(arr, n, d):
      
    # For handling k >= N
    i = 0
    j = 0
    d = d % n
  
    # Dividing the array into
    # number of sets
    no_of_sets = gcd(d, n)
  
    for i in range(no_of_sets):
        temp = arr[i]
        j = i
  
        # Rotate the array by Y
        while (True):
            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
def performQuery(arr, Q, q):
  
    N = len(arr)
  
    # Traverse each query
    for i in range(q):
  
        # If query of type X = 1
        if (Q[i][0] == 1):
            arr = RotateArr(arr, N, Q[i][1])
  
            # Print the array
            for t in arr:
                print(t, end = " ")
                  
            print()
  
        # If query of type X = 2
        else:
            print(MaxSum(arr, N, Q[i][1]))
  
# Driver Code
if __name__ == '__main__':
      
    # Given array arr[]
    arr = [ 1, 2, 3, 4, 5 ]
  
    q = 5
  
    # Given Queries
    Q = [ [ 1, 2 ], [ 2, 3 ],
          [ 1, 3 ], [ 1, 1 ],
          [ 2, 4 ] ]
  
    # Function call
    performQuery(arr, Q, q)
  
# This code is contributed by mohit kumar 29
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 *