El subarreglo más largo cuyos elementos se pueden igualar en incrementos máximos de K

Dado un arreglo arr[] de enteros positivos de tamaño N y un entero positivo K , la tarea es encontrar la longitud máxima posible de un subarreglo que se puede igualar agregando algún valor entero a cada elemento del subarreglo tal que la suma de los elementos agregados no excede K .

Ejemplos: 

Entrada: N = 5, arr[] = {1, 4, 9, 3, 6}, K = 9 
Salida:
Explicación: 
{1, 4} : {1+3, 4} = {4, 4} 
{ 4, 9} : {4+5, 9} = {9, 9} 
{3, 6} : {3+3, 6} = {6, 6} 
{9, 3, 6} : {9, 3+ 6, 6+3} = {9, 9, 9} 
Por lo tanto, la longitud máxima de dicho subarreglo es 3.

Entrada: N = 6, arr[] = {2, 4, 7, 3, 8, 5}, K = 10 
Salida:

Enfoque: Este problema se puede resolver usando programación dinámica

  • Inicializar: 
    • dp[] : Almacena la suma de elementos que se agregan al subarreglo.
    • deque : Almacena los índices del elemento máximo para cada subarreglo.
    • pos: Índice de la posición actual del subarreglo.
    • ans: Longitud del subarreglo máximo.
    • mx: elemento máximo de un subarreglo
    • pre: índice anterior del subarreglo actual.
  • Atraviese la array y verifique si el deque está vacío o no. En caso afirmativo, actualice el elemento máximo y el índice del elemento máximo junto con los índices de pre y pos .
  • Compruebe si el elemento agregado actualmente es mayor que K . En caso afirmativo, elimínelo de la array dp[] y actualice los índices de pos y pre .
  • Finalmente, actualice la longitud máxima del subarreglo válido.

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum
// possible length of subarray
int validSubArrLength(int arr[],
                      int N, int K)
{
    // Stores the sum of elements
    // that needs to be added to
    // the sub array
    int dp[N + 1];
 
    // Stores the index of the
    // current position of subarray
    int pos = 0;
 
    // Stores the maximum
    // length of subarray.
    int ans = 0;
 
    // Maximum element from
    // each subarray length
    int mx = 0;
 
    // Previous index of the
    // current subarray of
    // maximum length
    int pre = 0;
 
    // Deque to store the indices
    // of maximum element of
    // each sub array
    deque<int> q;
 
    // For each array element,
    // find the maximum length of
    // required subarray
    for (int i = 0; i < N; i++) {
        // Traverse the deque and
        // update the index of
        // maximum element.
        while (!q.empty()
               && arr[q.back()] < arr[i])
 
            q.pop_back();
 
        q.push_back(i);
 
        // If it is first element
        // then update maximum
        // and dp[]
        if (i == 0) {
            mx = arr[i];
            dp[i] = arr[i];
        }
 
        // Else check if current
        // element exceeds max
        else if (mx <= arr[i]) {
            // Update max and dp[]
            dp[i] = dp[i - 1] + arr[i];
            mx = arr[i];
        }
 
        else {
            dp[i] = dp[i - 1] + arr[i];
        }
 
        // Update the index of the
        // current maximum length
        // subarray
        if (pre == 0)
            pos = 0;
        else
            pos = pre - 1;
 
        // While current element
        // being added to dp[] array
        // exceeds K
        while ((i - pre + 1) * mx
                       - (dp[i] - dp[pos])
                   > K
               && pre < i) {
 
            // Update index of
            // current position and
            // the previous position
            pos = pre;
            pre++;
 
            // Remove elements
            // from deque and
            // update the
            // maximum element
            while (!q.empty()
                   && q.front() < pre
                   && pre < i) {
 
                q.pop_front();
                mx = arr[q.front()];
            }
        }
 
        // Update the maximum length
        // of the required subarray.
        ans = max(ans, i - pre + 1);
    }
    return ans;
}
 
// Driver Program
int main()
{
    int N = 6;
    int K = 8;
    int arr[] = { 2, 7, 1, 3, 4, 5 };
    cout << validSubArrLength(arr, N, K);
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG{
 
// Function to find maximum
// possible length of subarray
static int validSubArrLength(int arr[],
                             int N, int K)
{
    // Stores the sum of elements
    // that needs to be added to
    // the sub array
    int []dp = new int[N + 1];
 
    // Stores the index of the
    // current position of subarray
    int pos = 0;
 
    // Stores the maximum
    // length of subarray.
    int ans = 0;
 
    // Maximum element from
    // each subarray length
    int mx = 0;
 
    // Previous index of the
    // current subarray of
    // maximum length
    int pre = 0;
 
    // Deque to store the indices
    // of maximum element of
    // each sub array
    Deque<Integer> q = new LinkedList<>();
 
    // For each array element,
    // find the maximum length of
    // required subarray
    for(int i = 0; i < N; i++)
    {
         
       // Traverse the deque and
       // update the index of
       // maximum element.
       while (!q.isEmpty() &&
               arr[q.getLast()] < arr[i])
           q.removeLast();
       q.add(i);
        
       // If it is first element
       // then update maximum
       // and dp[]
       if (i == 0)
       {
           mx = arr[i];
           dp[i] = arr[i];
       }
        
       // Else check if current
       // element exceeds max
       else if (mx <= arr[i])
       {
            
           // Update max and dp[]
           dp[i] = dp[i - 1] + arr[i];
           mx = arr[i];
       }
       else
       {
           dp[i] = dp[i - 1] + arr[i];
       }
        
       // Update the index of the
       // current maximum length
       // subarray
       if (pre == 0)
           pos = 0;
       else
           pos = pre - 1;
        
       // While current element
       // being added to dp[] array
       // exceeds K
       while ((i - pre + 1) * mx -
          (dp[i] - dp[pos]) > K && pre < i)
       {
            
           // Update index of
           // current position and
           // the previous position
           pos = pre;
           pre++;
            
           // Remove elements from
           // deque and update the
           // maximum element
           while (!q.isEmpty() &&
                   q.peek() < pre && pre < i)
           {
               q.removeFirst();
               mx = arr[q.peek()];
           }
       }
        
       // Update the maximum length
       // of the required subarray.
       ans = Math.max(ans, i - pre + 1);
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 6;
    int K = 8;
    int arr[] = { 2, 7, 1, 3, 4, 5 };
     
    System.out.print(validSubArrLength(arr, N, K));
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 code for the above approach
 
# Function to find maximum
# possible length of subarray
def validSubArrLength(arr, N, K):
     
    # Stores the sum of elements
    # that needs to be added to
    # the sub array
    dp = [0 for i in range(N + 1)]
 
    # Stores the index of the
    # current position of subarray
    pos = 0
 
    # Stores the maximum
    # length of subarray.
    ans = 0
 
    # Maximum element from
    # each subarray length
    mx = 0
 
    # Previous index of the
    # current subarray of
    # maximum length
    pre = 0
 
    # Deque to store the indices
    # of maximum element of
    # each sub array
    q = []
 
    # For each array element,
    # find the maximum length of
    # required subarray
    for i in range(N):
         
        # Traverse the deque and
        # update the index of
        # maximum element.
        while (len(q) and arr[len(q) - 1] < arr[i]):
            q.remove(q[len(q) - 1])
 
        q.append(i)
 
        # If it is first element
        # then update maximum
        # and dp[]
        if (i == 0):
            mx = arr[i]
            dp[i] = arr[i]
 
        # Else check if current
        # element exceeds max
        elif (mx <= arr[i]):
             
            # Update max and dp[]
            dp[i] = dp[i - 1] + arr[i]
            mx = arr[i]
 
        else:
            dp[i] = dp[i - 1] + arr[i]
 
        # Update the index of the
        # current maximum length
        # subarray
        if (pre == 0):
            pos = 0
        else:
            pos = pre - 1
 
        # While current element
        # being added to dp[] array
        # exceeds K
        while ((i - pre + 1) *
               mx - (dp[i] - dp[pos]) > K and
              pre < i):
                   
            # Update index of
            # current position and
            # the previous position
            pos = pre
            pre += 1
 
            # Remove elements
            # from deque and
            # update the
            # maximum element
            while (len(q) and
                   q[0] < pre and
                   pre < i):
                q.remove(q[0])
                mx = arr[q[0]]
 
        # Update the maximum length
        # of the required subarray.
        ans = max(ans, i - pre + 1)
         
    return ans
 
# Driver code
if __name__ == '__main__':
     
    N = 6
    K = 8
     
    arr =  [ 2, 7, 1, 3, 4, 5 ]
     
    print(validSubArrLength(arr, N, K))
 
# This code is contributed by ipg2016107

Javascript

<script>
 
// Javascript code for the above approach
 
// Function to find maximum
// possible length of subarray
function validSubArrLength(arr, N, K)
{
    // Stores the sum of elements
    // that needs to be added to
    // the sub array
    var dp = Array(N+1);
 
    // Stores the index of the
    // current position of subarray
    var pos = 0;
 
    // Stores the maximum
    // length of subarray.
    var ans = 0;
 
    // Maximum element from
    // each subarray length
    var mx = 0;
 
    // Previous index of the
    // current subarray of
    // maximum length
    var pre = 0;
 
    // Deque to store the indices
    // of maximum element of
    // each sub array
    var q = [];
 
    // For each array element,
    // find the maximum length of
    // required subarray
    for (var i = 0; i < N; i++) {
        // Traverse the deque and
        // update the index of
        // maximum element.
        while (q.length!=0
               && arr[q[q.length-1]] < arr[i])
 
            q.pop();
 
        q.push(i);
 
        // If it is first element
        // then update maximum
        // and dp[]
        if (i == 0) {
            mx = arr[i];
            dp[i] = arr[i];
        }
 
        // Else check if current
        // element exceeds max
        else if (mx <= arr[i]) {
            // Update max and dp[]
            dp[i] = dp[i - 1] + arr[i];
            mx = arr[i];
        }
 
        else {
            dp[i] = dp[i - 1] + arr[i];
        }
 
        // Update the index of the
        // current maximum length
        // subarray
        if (pre == 0)
            pos = 0;
        else
            pos = pre - 1;
 
        // While current element
        // being added to dp[] array
        // exceeds K
        while ((i - pre + 1) * mx
                       - (dp[i] - dp[pos])
                   > K
               && pre < i) {
 
            // Update index of
            // current position and
            // the previous position
            pos = pre;
            pre++;
 
            // Remove elements
            // from deque and
            // update the
            // maximum element
            while (q.length!=0
                   && q[0] < pre
                   && pre < i) {
 
                q.shift();
                mx = arr[q[0]];
            }
        }
 
        // Update the maximum length
        // of the required subarray.
        ans = Math.max(ans, i - pre + 1);
    }
    return ans;
}
 
// Driver Program
var N = 6;
var K = 8;
var arr = [2, 7, 1, 3, 4, 5];
document.write( validSubArrLength(arr, N, K));
 
 
</script>

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to find maximum
    // possible length of subarray
    static int validSubArrLength(int[] arr, int N, int K)
    {
        // Stores the sum of elements
        // that needs to be added to
        // the sub array
        int[] dp = new int[N + 1];
 
        // Stores the index of the
        // current position of subarray
        int pos = 0;
 
        // Stores the maximum
        // length of subarray.
        int ans = 0;
 
        // Maximum element from
        // each subarray length
        int mx = 0;
 
        // Previous index of the
        // current subarray of
        // maximum length
        int pre = 0;
 
        // Deque to store the indices
        // of maximum element of
        // each sub array
        List<int> q = new List<int>();
 
        // For each array element,
        // find the maximum length of
        // required subarray
        for(int i = 0 ; i < N ; i++)
        {
             
            // Traverse the deque and
            // update the index of
            // maximum element.
            while (q.Count > 0 && arr[q[q.Count - 1]] < arr[i]){
                q.RemoveAt(q.Count - 1);
            }
            q.Add(i);
                 
            // If it is first element
            // then update maximum
            // and dp[]
            if (i == 0)
            {
                mx = arr[i];
                dp[i] = arr[i];
            }
                 
            // Else check if current
            // element exceeds max
            else if (mx <= arr[i])
            {
                     
                // Update max and dp[]
                dp[i] = dp[i - 1] + arr[i];
                mx = arr[i];
            }
            else
            {
                dp[i] = dp[i - 1] + arr[i];
            }
                 
            // Update the index of the
            // current maximum length
            // subarray
            if (pre == 0)
                pos = 0;
            else
                pos = pre - 1;
                 
            // While current element
            // being added to dp[] array
            // exceeds K
            while ((i - pre + 1) * mx - (dp[i] - dp[pos]) > K && pre < i)
            {
                     
                // Update index of
                // current position and
                // the previous position
                pos = pre;
                pre++;
                     
                // Remove elements from
                // deque and update the
                // maximum element
                while (q.Count > 0 && q[0] < pre && pre < i)
                {
                    q.RemoveAt(0);
                    mx = arr[q[0]];
                }
            }
                 
            // Update the maximum length
            // of the required subarray.
            ans = Math.Max(ans, i - pre + 1);
        }
        return ans;
    }
 
    // Driver code
    public static void Main(string[] args){
 
        int N = 6;
        int K = 8;
        int[] arr = new int[]{ 2, 7, 1, 3, 4, 5 };
         
        Console.WriteLine(validSubArrLength(arr, N, K));
 
    }
}
Producción: 

4

 

Complejidad de Tiempo: O(N 2
Complejidad de Espacio Auxiliar: O(N) 
 

Publicación traducida automáticamente

Artículo escrito por Samdare B 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 *