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:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the maximum
// sum of length k
int MaxSum(vector<int> arr, int n,
int k)
{
int 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
int gcd(int n1, int 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
vector<int> RotateArr(vector<int> arr,
int n, int d)
{
// For handling k >= N
int i = 0, j = 0;
d = d % n;
// Dividing the array into
// number of sets
int no_of_sets = gcd(d, n);
for (i = 0; i < no_of_sets; i++) {
int temp = arr[i];
j = i;
// Rotate the array by Y
while (true) {
int 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
void performQuery(vector<int>& arr,
int Q[][2], int q)
{
int N = (int)arr.size();
// Traverse each query
for (int i = 0; i < q; i++) {
// If query of type X = 1
if (Q[i][0] == 1) {
arr = RotateArr(arr, N,
Q[i][1]);
// Print the array
for (auto t : arr) {
cout << t << " ";
}
cout << "
";
}
// If query of type X = 2
else {
cout << MaxSum(arr, N, Q[i][1])
<< "
";
}
}
}
// Driver Code
int main()
{
// Given array arr[]
vector<int> arr = { 1, 2, 3, 4, 5 };
int q = 5;
// Given Queries
int Q[][2] = { { 1, 2 }, { 2, 3 },
{ 1, 3 }, { 1, 1 },
{ 2, 4 }
};
// Function Call
performQuery(arr, Q, q);
return 0;
}
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