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: 3
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: 4
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)