Dado un arreglo A[] que consta de N enteros y un entero K , la tarea es maximizar la longitud del subarreglo que tiene elementos iguales después de realizar como máximo K incrementos de 1 en los elementos del arreglo.
Nota: el mismo elemento de array se puede incrementar más de una vez.
Ejemplos:
Entrada: A[] = {2, 4, 8, 5, 9, 6}, K = 6
Salida: 3
Explicación:
El subarreglo [8, 5, 9] se puede modificar a [9, 9, 9].
El número total de incrementos requeridos es 5, que es menor que K(= 6).Entrada: A[] = {2, 2, 4}, K = 10
Salida: 3
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y, para cada subarreglo, verificar si todos sus elementos se pueden hacer iguales en incrementos de K como máximo. Imprime la longitud máxima de dichos subarreglos obtenidos.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque: El enfoque anterior se puede optimizar utilizando la técnica de la ventana deslizante . Siga los pasos a continuación para resolver el problema:
- Mantenga un registro del elemento máximo de la ventana.
- El total de operaciones requeridas para una ventana en particular se obtiene mediante la siguiente ecuación:
Recuento de operaciones = (Longitud de la ventana calculada hasta el momento + 1) * (Elemento máximo de la ventana) – Suma de la ventana
- Ahora, verifique si el valor calculado anteriormente excede K o no. Si es así, deslice el puntero de inicio de la ventana hacia la derecha; de lo contrario, incremente la longitud de la ventana calculada hasta el momento.
- Repita los pasos anteriores para obtener la ventana más larga que satisfaga la condición requerida.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++14 program for above approach #include <bits/stdc++.h> using namespace std; #define newl "\n" // Function to find the maximum length // of subarray of equal elements after // performing at most K increments int maxSubarray(int a[], int k, int n) { // Stores the size // of required subarray int answer = 0; // Starting point of a window int start = 0; // Stores the sum of window long int s = 0; deque<int> dq; // Iterate over array for(int i = 0; i < n; i++) { // Current element int x = a[i]; // Remove index of minimum elements // from deque which are less than // the current element while (!dq.empty() && a[dq.front()] <= x) dq.pop_front(); // Insert current index in deque dq.push_back(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal long int cost = (long int)a[dq.front()] * (answer + 1) - s; // If cost is less than k if (cost <= (long int)k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq.front() == start) dq.pop_front(); s -= a[start++]; } } // Return answer return answer; } // Driver Code int main() { int a[] = { 2, 2, 4 }; int k = 10; // Length of array int n = sizeof(a) / sizeof(a[0]); cout << (maxSubarray(a, k, n)); return 0; } // This code is contributed by jojo9911
Java
// Java Program for above approach import java.util.*; class GFG { // Function to find the maximum length // of subarray of equal elements after // performing at most K increments static int maxSubarray(int[] a, int k) { // Length of array int n = a.length; // Stores the size // of required subarray int answer = 0; // Starting point of a window int start = 0; // Stores the sum of window long s = 0; Deque<Integer> dq = new LinkedList<>(); // Iterate over array for (int i = 0; i < n; i++) { // Current element int x = a[i]; // Remove index of minimum elements // from deque which are less than // the current element while (!dq.isEmpty() && a[dq.peek()] <= x) dq.poll(); // Insert current index in deque dq.add(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal long cost = (long)a[dq.peekFirst()] * (answer + 1) - s; // If cost is less than k if (cost <= (long)k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq.peekFirst() == start) dq.pollFirst(); s -= a[start++]; } } // Return answer return answer; } // Driver Code public static void main(String[] args) { int[] a = { 2, 2, 4 }; int k = 10; // Function call System.out.println(maxSubarray(a, k)); } }
Python3
# Python3 program for above approach from collections import deque # Function to find the maximum length # of subarray of equal elements after # performing at most K increments def maxSubarray(a, k): # Length of array n = len(a) # Stores the size # of required subarray answer = 0 # Starting po of a window start = 0 # Stores the sum of window s = 0 dq = deque() # Iterate over array for i in range(n): # Current element x = a[i] # Remove index of minimum elements # from deque which are less than # the current element while (len(dq) > 0 and a[dq[-1]] <= x): dq.popleft() # Insert current index in deque dq.append(i) # Update current window sum s += x # Calculate required operation to # make current window elements equal cost = a[dq[0]] * (answer + 1) - s # If cost is less than k if (cost <= k): answer += 1 # Shift window start pointer towards # right and update current window sum else: if (dq[0] == start): dq.popleft() s -= a[start] start += 1 # Return answer return answer # Driver Code if __name__ == '__main__': a = [ 2, 2, 4 ] k = 10 # Function call print(maxSubarray(a, k)) # This code is contributed by mohit kumar 29
C#
// C# Program for // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find the maximum length // of subarray of equal elements after // performing at most K increments static int maxSubarray(int[] a, int k) { // Length of array int n = a.Length; // Stores the size // of required subarray int answer = 0; // Starting point of a window int start = 0; // Stores the sum of window long s = 0; Queue<int> dq = new Queue<int>(); // Iterate over array for (int i = 0; i < n; i++) { // Current element int x = a[i]; // Remove index of minimum // elements from deque // which are less than // the current element while (dq.Count!=0 && a[dq.Peek()] <= x) dq.Dequeue(); // Insert current // index in deque dq.Enqueue(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal long cost = (long)a[dq.Peek()] * (answer + 1) - s; // If cost is less than k if (cost <= (long)k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq.Peek() == start) dq.Dequeue(); s -= a[start++]; } } // Return answer return answer; } // Driver Code public static void Main(String[] args) { int[] a = {2, 2, 4}; int k = 10; // Function call Console.WriteLine(maxSubarray(a, k)); } } // This code is contributed by gauravrajput1
Javascript
<script> // Javascript program for above approach // Function to find the maximum length // of subarray of equal elements after // performing at most K increments function maxSubarray(a, k, n) { // Stores the size // of required subarray var answer = 0; // Starting point of a window var start = 0; // Stores the sum of window var s = 0; var dq = []; // Iterate over array for(var i = 0; i < n; i++) { // Current element var x = a[i]; // Remove index of minimum elements // from deque which are less than // the current element while (dq.length!=0 && a[dq[0]] <= x) dq.shift(); // Insert current index in deque dq.push(i); // Update current window sum s += x; // Calculate required operation to // make current window elements equal var cost = a[dq[0]] * (answer + 1) - s; // If cost is less than k if (cost <= k) answer++; // Shift window start pointer towards // right and update current window sum else { if (dq[0] == start) dq.shift(); s -= a[start++]; } } // Return answer return answer; } // Driver Code var a = [2, 2, 4]; var k = 10; // Length of array var n = a.length; document.write(maxSubarray(a, k, n)); </script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)