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 12Entrada: 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:
- Si X = 1 , gire la array por Y , utilizando el algoritmo de malabarismo .
- De lo contrario, si X = 2 , encuentre el subarreglo de suma máxima de longitud Y utilizando la técnica de ventana deslizante.
- Imprima la array si la consulta X es 1 .
- 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
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