Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar la longitud del subarreglo más largo que consta de los mismos elementos que se pueden obtener al disminuir los elementos de la array en 1 como máximo K veces.
Ejemplo:
Entrada: arr[] = { 1, 2, 3 }, K = 1
Salida: 2
Explicación:
Decrementar arr[0] en 1 modifica arr[] a { 1, 1, 3 }
El subarreglo más largo con elementos iguales es { 1 , 1 }.
Por lo tanto, la salida requerida es 2.Entrada: arr[] = { 1, 7, 3, 4, 5, 6 }, K = 6
Salida: 4
Enfoque: el problema se puede resolver utilizando el árbol de segmentos y la técnica de búsqueda binaria . La idea es utilizar las siguientes observaciones:
Número total de operaciones de decremento requeridas para hacer que todos los elementos de la array del subarreglo { array[inicio], …, array[final] } sean iguales
= (Σ(inicio, final)) – (final – inicio + 1) * (valor_mínimo)donde, inicio = índice del punto inicial del subarreglo
end = índice del punto final del
subarreglo min_value = valor más pequeño del índice i al j
Σ(start, end) = suma de todos los elementos del índice i al j
Siga los pasos a continuación para resolver el problema anterior:
- Inicialice un árbol de segmentos para calcular el elemento más pequeño en un subarreglo del arreglo y un arreglo de suma de prefijos para calcular los elementos de suma de un subarreglo.
- Atraviesa la array , arr[] . Para cada i -ésimo elemento realice las siguientes operaciones:
- Inicialice dos variables, digamos, start = i , end = N – 1 y aplique la búsqueda binaria en el rango [start, end] para comprobar si todos los elementos del subarreglo { arr[start], …, arr[end] } pueden igualarse o no decrementando como máximo K operaciones a partir de las observaciones anteriores.
- Si todos los elementos del subarreglo { arr[start], …, arr[end] } se pueden hacer iguales decrementando como máximo K operaciones, entonces actualice start = (start + end) / 2 + 1 .
- De lo contrario, actualice fin = (inicio + fin) / 2 – 1
- Finalmente, imprima la longitud del subarreglo más largo obtenido de las operaciones anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to construct Segment Tree
// to return the minimum element in a range
int build(int tree[], int* A, int start,
int end, int node)
{
// If leaf nodes of
// the tree are found
if (start == end) {
// Update the value in segment
// tree from given array
tree[node] = A[start];
return tree[node];
}
// Divide left and right subtree
int mid = (start + end) / 2;
// Stores smallest element in
// subarray { arr[start], arr[mid] }
int X = build(tree, A, start, mid,
2 * node + 1);
// Stores smallest element in
// subarray { arr[mid + 1], arr[end] }
int Y = build(tree, A, mid + 1,
end, 2 * node + 2);
// Stores smallest element in
// subarray { arr[start], arr[end] }
return tree[node] = min(X, Y);
}
// Function to find the smallest
// element present in a subarray
int query(int tree[], int start, int end,
int l, int r, int node)
{
// If elements of the subarray
// are not in the range [l, r]
if (start > r || end < l)
return INT_MAX;
// If all the elements of the
// subarray are in the range [l, r]
if (start >= l && end <= r)
return tree[node];
// Divide tree into left
// and right subtree
int mid = (start + end) / 2;
// Stores smallest element
// in left subtree
int X = query(tree, start, mid, l,
r, 2 * node + 1);
// Stores smallest element in
// right subtree
int Y = query(tree, mid + 1, end, l,
r, 2 * node + 2);
return min(X, Y);
}
// Function that find length of longest
// subarray with all equal elements in
// atmost K decrements
int longestSubArray(int* A, int N, int K)
{
// Stores length of longest subarray
// with all equal elements in atmost
// K decrements.
int res = 1;
// Store the prefix sum array
int preSum[N + 1];
// Calculate the prefix sum array
preSum[0] = A[0];
for (int i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
int tree[4 * N + 5];
// Build the segment tree
// for range min query
build(tree, A, 0, N - 1, 0);
// Traverse the array
for (int i = 0; i < N; i++) {
// Stores start index
// of the subarray
int start = i;
// Stores end index
// of the subarray
int end = N - 1;
int mid;
// Stores end index of
// the longest subarray
int max_index = i;
// Performing the binary search
// to find the endpoint
// for the selected range
while (start <= end) {
// Find the mid for binary search
mid = (start + end) / 2;
// Find the smallest element in
// range [i, mid] using Segment Tree
int min_element
= query(tree, 0, N - 1, i, mid, 0);
// Stores total sum of subarray
// after K decrements
int expected_sum
= (mid - i + 1) * min_element;
// Stores sum of elements of
// subarray before K decrements
int actual_sum
= preSum[mid + 1] - preSum[i];
// If subarray found with
// all equal elements
if (actual_sum - expected_sum <= K) {
// Update start
start = mid + 1;
// Update max_index
max_index = max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else {
// Update end
end = mid - 1;
}
}
// Store the length of longest subarray
res = max(res, max_index - i + 1);
}
// Return result
return res;
}
// Driver Code
int main()
{
int arr[] = { 1, 7, 3, 4, 5, 6 };
int k = 6;
int n = 6;
cout << longestSubArray(arr, n, k);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to construct Segment Tree
// to return the minimum element in a range
static int build(int tree[], int[] A, int start,
int end, int node)
{
// If leaf nodes of
// the tree are found
if (start == end)
{
// Update the value in segment
// tree from given array
tree[node] = A[start];
return tree[node];
}
// Divide left and right subtree
int mid = (start + end) / 2;
// Stores smallest element in
// subarray { arr[start], arr[mid] }
int X = build(tree, A, start, mid,
2 * node + 1);
// Stores smallest element in
// subarray { arr[mid + 1], arr[end] }
int Y = build(tree, A, mid + 1,
end, 2 * node + 2);
// Stores smallest element in
// subarray { arr[start], arr[end] }
return (tree[node] = Math.min(X, Y));
}
// Function to find the smallest
// element present in a subarray
static int query(int tree[], int start, int end,
int l, int r, int node)
{
// If elements of the subarray
// are not in the range [l, r]
if (start > r || end < l)
return Integer.MAX_VALUE;
// If all the elements of the
// subarray are in the range [l, r]
if (start >= l && end <= r)
return tree[node];
// Divide tree into left
// and right subtree
int mid = (start + end) / 2;
// Stores smallest element
// in left subtree
int X = query(tree, start, mid, l,
r, 2 * node + 1);
// Stores smallest element in
// right subtree
int Y = query(tree, mid + 1, end, l,
r, 2 * node + 2);
return Math.min(X, Y);
}
// Function that find length of longest
// subarray with all equal elements in
// atmost K decrements
static int longestSubArray(int[] A, int N, int K)
{
// Stores length of longest subarray
// with all equal elements in atmost
// K decrements.
int res = 1;
// Store the prefix sum array
int preSum[] = new int[N + 1];
// Calculate the prefix sum array
preSum[0] = A[0];
for(int i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
int tree[] = new int[4 * N + 5];
// Build the segment tree
// for range min query
build(tree, A, 0, N - 1, 0);
// Traverse the array
for(int i = 0; i < N; i++)
{
// Stores start index
// of the subarray
int start = i;
// Stores end index
// of the subarray
int end = N - 1;
int mid;
// Stores end index of
// the longest subarray
int max_index = i;
// Performing the binary search
// to find the endpoint
// for the selected range
while (start <= end)
{
// Find the mid for binary search
mid = (start + end) / 2;
// Find the smallest element in
// range [i, mid] using Segment Tree
int min_element = query(tree, 0, N - 1,
i, mid, 0);
// Stores total sum of subarray
// after K decrements
int expected_sum = (mid - i + 1) *
min_element;
// Stores sum of elements of
// subarray before K decrements
int actual_sum = preSum[mid + 1] -
preSum[i];
// If subarray found with
// all equal elements
if (actual_sum - expected_sum <= K)
{
// Update start
start = mid + 1;
// Update max_index
max_index = Math.max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else
{
// Update end
end = mid - 1;
}
}
// Store the length of longest subarray
res = Math.max(res, max_index - i + 1);
}
// Return result
return res;
}
// Driver Code
static public void main(String args[])
{
int arr[] = { 1, 7, 3, 4, 5, 6 };
int k = 6;
int n = 6;
System.out.print(longestSubArray(arr, n, k));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program to implement # the above approach import sys # Function to construct Segment Tree # to return the minimum element in a range def build(tree, A, start, end, node): # If leaf nodes of # the tree are found if (start == end): # Update the value in segment # tree from given array tree[node] = A[start] return tree[node] # Divide left and right subtree mid = (int)((start + end) / 2) # Stores smallest element in # subarray : arr[start], arr[mid] X = build(tree, A, start, mid, 2 * node + 1) # Stores smallest element in # subarray : arr[mid + 1], arr[end] Y = build(tree, A, mid + 1, end, 2 * node + 2) # Stores smallest element in # subarray : arr[start], arr[end] return (tree[node] == min(X, Y)) # Function to find the smallest # element present in a subarray def query(tree, start, end, l, r, node): # If elements of the subarray # are not in the range [l, r] if (start > r or end < l) : return sys.maxsize # If all the elements of the # subarray are in the range [l, r] if (start >= l and end <= r): return tree[node] # Divide tree into left # and right subtree mid = (int)((start + end) / 2) # Stores smallest element # in left subtree X = query(tree, start, mid, l, r, 2 * node + 1) # Stores smallest element in # right subtree Y = query(tree, mid + 1, end, l, r, 2 * node + 2) return min(X, Y) # Function that find length of longest # subarray with all equal elements in # atmost K decrements def longestSubArray(A, N, K): # Stores length of longest subarray # with all equal elements in atmost # K decrements. res = 1 # Store the prefix sum array preSum = [0] * (N + 1) # Calculate the prefix sum array preSum[0] = A[0] for i in range(N): preSum[i + 1] = preSum[i] + A[i] tree = [0] * (4 * N + 5) # Build the segment tree # for range min query build(tree, A, 0, N - 1, 0) # Traverse the array for i in range(N): # Stores start index # of the subarray start = i # Stores end index # of the subarray end = N - 1 # Stores end index of # the longest subarray max_index = i # Performing the binary search # to find the endpoint # for the selected range while (start <= end): # Find the mid for binary search mid = (int)((start + end) / 2) # Find the smallest element in # range [i, mid] using Segment Tree min_element = query(tree, 0, N - 1, i, mid, 0) # Stores total sum of subarray # after K decrements expected_sum = (mid - i + 1) * min_element # Stores sum of elements of # subarray before K decrements actual_sum = preSum[mid + 1] - preSum[i] # If subarray found with # all equal elements if (actual_sum - expected_sum <= K): # Update start start = mid + 1 # Update max_index max_index = max(max_index, mid) # If false, it means that # the selected range is invalid else: # Update end end = mid - 1 # Store the length of longest subarray res = max(res, max_index - i + 2) # Return result return res # Driver Code arr = [ 1, 7, 3, 4, 5, 6 ] k = 6 n = 6 print(longestSubArray(arr, n, k)) # This code is contributed by splevel62
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to construct Segment Tree
// to return the minimum element in a range
static int build(int[] tree, int[] A, int start,
int end, int node)
{
// If leaf nodes of
// the tree are found
if (start == end)
{
// Update the value in segment
// tree from given array
tree[node] = A[start];
return tree[node];
}
// Divide left and right subtree
int mid = (start + end) / 2;
// Stores smallest element in
// subarray { arr[start], arr[mid] }
int X = build(tree, A, start, mid,
2 * node + 1);
// Stores smallest element in
// subarray { arr[mid + 1], arr[end] }
int Y = build(tree, A, mid + 1,
end, 2 * node + 2);
// Stores smallest element in
// subarray { arr[start], arr[end] }
return (tree[node] = Math.Min(X, Y));
}
// Function to find the smallest
// element present in a subarray
static int query(int[] tree, int start, int end,
int l, int r, int node)
{
// If elements of the subarray
// are not in the range [l, r]
if (start > r || end < l)
return Int32.MaxValue;
// If all the elements of the
// subarray are in the range [l, r]
if (start >= l && end <= r)
return tree[node];
// Divide tree into left
// and right subtree
int mid = (start + end) / 2;
// Stores smallest element
// in left subtree
int X = query(tree, start, mid, l,
r, 2 * node + 1);
// Stores smallest element in
// right subtree
int Y = query(tree, mid + 1, end, l,
r, 2 * node + 2);
return Math.Min(X, Y);
}
// Function that find length of longest
// subarray with all equal elements in
// atmost K decrements
static int longestSubArray(int[] A, int N, int K)
{
// Stores length of longest subarray
// with all equal elements in atmost
// K decrements.
int res = 1;
// Store the prefix sum array
int[] preSum = new int[N + 1];
// Calculate the prefix sum array
preSum[0] = A[0];
for(int i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
int[] tree = new int[4 * N + 5];
// Build the segment tree
// for range min query
build(tree, A, 0, N - 1, 0);
// Traverse the array
for(int i = 0; i < N; i++)
{
// Stores start index
// of the subarray
int start = i;
// Stores end index
// of the subarray
int end = N - 1;
int mid;
// Stores end index of
// the longest subarray
int max_index = i;
// Performing the binary search
// to find the endpoint
// for the selected range
while (start <= end)
{
// Find the mid for binary search
mid = (start + end) / 2;
// Find the smallest element in
// range [i, mid] using Segment Tree
int min_element = query(tree, 0, N - 1,
i, mid, 0);
// Stores total sum of subarray
// after K decrements
int expected_sum = (mid - i + 1) *
min_element;
// Stores sum of elements of
// subarray before K decrements
int actual_sum = preSum[mid + 1] -
preSum[i];
// If subarray found with
// all equal elements
if (actual_sum - expected_sum <= K)
{
// Update start
start = mid + 1;
// Update max_index
max_index = Math.Max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else
{
// Update end
end = mid - 1;
}
}
// Store the length of longest subarray
res = Math.Max(res, max_index - i + 1);
}
// Return result
return res;
}
// Driver Code
static void Main()
{
int[] arr = { 1, 7, 3, 4, 5, 6 };
int k = 6;
int n = 6;
Console.WriteLine(longestSubArray(arr, n, k));
}
}
// This code is contributed by susmitakundugoaldanga
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to construct Segment Tree
// to return the minimum element in a range
function build(tree,A, start,end, node)
{
// If leaf nodes of
// the tree are found
if (start == end) {
// Update the value in segment
// tree from given array
tree[node] = A[start];
return tree[node];
}
// Divide left and right subtree
let mid = Math.floor((start + end) / 2);
// Stores smallest element in
// subarray { arr[start], arr[mid] }
let X = build(tree, A, start, mid,
2 * node + 1);
// Stores smallest element in
// subarray { arr[mid + 1], arr[end] }
let Y = build(tree, A, mid + 1,
end, 2 * node + 2);
// Stores smallest element in
// subarray { arr[start], arr[end] }
return tree[node] = Math.min(X, Y);
}
// Function to find the smallest
// element present in a subarray
function query(tree,start, end,l, r, node)
{
// If elements of the subarray
// are not in the range [l, r]
if (start > r || end < l)
return Number.MAX_VALUE;
// If all the elements of the
// subarray are in the range [l, r]
if (start >= l && end <= r)
return tree[node];
// Divide tree into left
// and right subtree
let mid = Math.floor((start + end) / 2);
// Stores smallest element
// in left subtree
let X = query(tree, start, mid, l,
r, 2 * node + 1);
// Stores smallest element in
// right subtree
let Y = query(tree, mid + 1, end, l,
r, 2 * node + 2);
return Math.min(X, Y);
}
// Function that find length of longest
// subarray with all equal elements in
// atmost K decrements
function longestSubArray(A,N,K)
{
// Stores length of longest subarray
// with all equal elements in atmost
// K decrements.
let res = 1;
// Store the prefix sum array
let preSum = new Array(N + 1);
// Calculate the prefix sum array
preSum[0] = A[0];
for (let i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
let tree = new Array(4 * N + 5);
// Build the segment tree
// for range min query
build(tree, A, 0, N - 1, 0);
// Traverse the array
for (let i = 0; i < N; i++) {
// Stores start index
// of the subarray
let start = i;
// Stores end index
// of the subarray
let end = N - 1;
let mid;
// Stores end index of
// the longest subarray
let max_index = i;
// Performing the binary search
// to find the endpoint
// for the selected range
while (start <= end) {
// Find the mid for binary search
mid = Math.floor((start + end) / 2);
// Find the smallest element in
// range [i, mid] using Segment Tree
let min_element
= query(tree, 0, N - 1, i, mid, 0);
// Stores total sum of subarray
// after K decrements
let expected_sum
= (mid - i + 1) * min_element;
// Stores sum of elements of
// subarray before K decrements
let actual_sum
= preSum[mid + 1] - preSum[i];
// If subarray found with
// all equal elements
if (actual_sum - expected_sum <= K) {
// Update start
start = mid + 1;
// Update max_index
max_index = Math.max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else {
// Update end
end = mid - 1;
}
}
// Store the length of longest subarray
res = Math.max(res, max_index - i + 1);
}
// Return result
return res;
}
// Driver Code
let arr = [ 1, 7, 3, 4, 5, 6 ];
let k = 6;
let n = 6;
document.write(longestSubArray(arr, n, k),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
4
Complejidad de tiempo: O(N * (log(N)) 2 )
Espacio auxiliar: O(N)
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por harshjangid y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA