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:
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>
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