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>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)