Maximice la longitud del subarreglo de elementos iguales realizando como máximo K operaciones de incremento

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)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *