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 << "\n";
}
// If query of type X = 2
else {
cout << MaxSum(arr, N, Q[i][1])
<< "\n";
}
}
}
// 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;
}
Java
// Java program for
// the above approach
class GFG{
// Function to calculate the maximum
// sum of length k
static int MaxSum(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
static 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
static int []RotateArr(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
static void performQuery(int []arr,
int Q[][], int q)
{
int N = arr.length;
// 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 (int t : arr)
{
System.out.print(t + " ");
}
System.out.print("\n");
}
// If query of type X = 2
else
{
System.out.print(MaxSum(arr, N,
Q[i][1]) + "\n");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int []arr = {1, 2, 3, 4, 5};
int q = 5;
// Given Queries
int Q[][] = {{1, 2}, {2, 3},
{1, 3}, {1, 1},
{2, 4}};
// Function Call
performQuery(arr, Q, q);
}
}
// This code is contributed by Rajput-Ji
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
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate the maximum
// sum of length k
static int MaxSum(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
static 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
static int []RotateArr(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
static void performQuery(int[] arr,
int[,] Q, int q)
{
int N = arr.Length;
// 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(int t = 0; t < arr.Length; t++)
{
Console.Write(arr[t] + " ");
}
Console.WriteLine();
}
// If query of type X = 2
else
{
Console.WriteLine(MaxSum(arr, N,
Q[i, 1]));
}
}
}
// Driver code
static void Main()
{
// Given array arr[]
int[] arr = { 1, 2, 3, 4, 5 };
int q = 5;
// Given Queries
int[,] Q = { { 1, 2 }, { 2, 3 },
{ 1, 3 }, { 1, 1 },
{ 2, 4 } };
// Function call
performQuery(arr, Q, q);
}
}
// This code is contributed by divyeshrabadiya07
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)
Publicación traducida automáticamente
Artículo escrito por shawavisek35 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA