Dada una array de enteros arr y un número K , la tarea es encontrar la longitud del subarreglo más largo de modo que todos los elementos en este subarreglo puedan hacerse iguales en incrementos de K como máximo.
Ejemplos:
Entrada: arr[] = {2, 0, 4, 6, 7}, K = 6
Salida: 3
El subarreglo más largo es {2, 0, 4} que se puede hacer como {4, 4, 4} con incrementos totales = 6 ( ≤ K )Entrada: arr[] = {12, 10, 16, 20, 7, 11}, K = 25
Salida: 4
El subarreglo más largo es {12, 10, 16, 20} que se puede hacer como {20, 20, 20 , 20} con incrementos totales = 22 ( ≤ K )
Acercarse:
- Se utilizará una variable i para almacenar el punto de inicio del subarreglo más largo requerido y una variable j para el punto final. Por lo tanto, el rango será [i, j]
- Inicialmente, asuma que el rango válido es [0, N).
- El rango real [i, j] se calculará mediante la búsqueda binaria . Por cada búsqueda realizada:
- Se puede usar un árbol de segmentos para encontrar el elemento máximo en el rango [i, j]
- Haga que todos los elementos en el rango [i, j] sean iguales al elemento máximo encontrado.
- Luego, use una array de suma de prefijos para obtener la suma de los elementos en el rango [i, j].
- Entonces, el número de incrementos requeridos en este rango se puede calcular como:
Total number of increments
= (j - i + 1) * (max_value) - Σ(i, j)
where i = index of the starting point of the subarray
j = index of end point of subarray
max_value = maximum value from index i to j
Σ(i, j) = sum of all elements from index i to j
- Si el número de incrementos requeridos es menor o igual a K , es un subarreglo válido; de lo contrario, no es válido.
- Para subarreglo inválido, actualice los puntos de inicio y finalización en consecuencia para la próxima búsqueda binaria
- Devuelve la longitud del rango de subarreglo más largo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of
// Longest Subarray with same elements
// in atmost K increments
#include <bits/stdc++.h>
using namespace std;
// Initialize array for segment tree
int segment_tree[4 * 1000000];
// Function that builds the segment
// tree to return the max element
// in a range
int build(int* A, int start, int end,
int node)
{
if (start == end)
// update the value in segment
// tree from given array
segment_tree[node] = A[start];
else {
// find the middle index
int mid = (start + end) / 2;
// If there are more than one
// elements, then recur for left
// and right subtrees and
// store the max of values in this node
segment_tree[node]
= max(
build(A, start, mid, 2 * node + 1),
build(A, mid + 1, end, 2 * node + 2));
}
return segment_tree[node];
}
// Function to return the max
// element in the given range
int query(int start, int end, int l, int r,
int node)
{
// If the range is out of bounds,
// return -1
if (start > r || end < l)
return -1;
if (start >= l && end <= r)
return segment_tree[node];
int mid = (start + end) / 2;
return max(query(start, mid, l,
r, 2 * node + 1),
query(mid + 1, end, l,
r, 2 * node + 2));
}
// Function that returns length of longest
// subarray with same elements in atmost
// K increments.
int longestSubArray(int* A, int N, int K)
{
// Initialize the result variable
// Even though the K is 0,
// the required longest subarray,
// in that case, will also be of length 1
int res = 1;
// Initialize the prefix sum array
int preSum[N + 1];
// Build the prefix sum array
preSum[0] = A[0];
for (int i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
// Build the segment tree
// for range max query
build(A, 0, N - 1, 0);
// Loop through the array
// with a starting point as i
// for the required subarray till
// the longest subarray is found
for (int i = 0; i < N; i++) {
int start = i, end = N - 1,
mid, 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 max element
// in the range [i, mid]
// using Segment Tree
int max_element
= query(0, N - 1,
i, mid, 0);
// Total sum of subarray after increments
int expected_sum = (mid - i + 1)
* max_element;
// Actual sum of elements
// before increments
int actual_sum = preSum[mid + 1]
- preSum[i];
// Check if such increment is possible
// If true, then current i
// is the actual starting point
// of the required longest subarray
if (expected_sum - actual_sum <= K) {
// Now for finding the endpoint
// for this range
// Perform the Binary search again
// with the updated start
start = mid + 1;
// Store max end point for the range
// to give longest subarray
max_index = max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else {
// Perform the Binary Search again
// with the updated 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[] = { 2, 0, 4, 6, 7 }, K = 6;
int N = sizeof(arr) / sizeof(arr[0]);
cout << longestSubArray(arr, N, K);
return 0;
}
Java
// Java program to find the length of
// Longest Subarray with same elements
// in atmost K increments
class GFG
{
// Initialize array for segment tree
static int segment_tree[] = new int[4 * 1000000];
// Function that builds the segment
// tree to return the max element
// in a range
static int build(int A[], int start, int end,
int node)
{
if (start == end)
// update the value in segment
// tree from given array
segment_tree[node] = A[start];
else
{
// find the middle index
int mid = (start + end) / 2;
// If there are more than one
// elements, then recur for left
// and right subtrees and
// store the max of values in this node
segment_tree[node] = Math.max(
build(A, start, mid, 2 * node + 1),
build(A, mid + 1, end, 2 * node + 2));
}
return segment_tree[node];
}
// Function to return the max
// element in the given range
static int query(int start, int end, int l, int r,
int node)
{
// If the range is out of bounds,
// return -1
if (start > r || end < l)
return -1;
if (start >= l && end <= r)
return segment_tree[node];
int mid = (start + end) / 2;
return Math.max(query(start, mid, l,
r, 2 * node + 1),
query(mid + 1, end, l,
r, 2 * node + 2));
}
// Function that returns length of longest
// subarray with same elements in atmost
// K increments.
static int longestSubArray(int A[], int N, int K)
{
// Initialize the result variable
// Even though the K is 0,
// the required longest subarray,
// in that case, will also be of length 1
int res = 1;
// Initialize the prefix sum array
int preSum[] = new int[N + 1];
// Build the prefix sum array
preSum[0] = A[0];
for (int i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
// Build the segment tree
// for range max query
build(A, 0, N - 1, 0);
// Loop through the array
// with a starting point as i
// for the required subarray till
// the longest subarray is found
for (int i = 0; i < N; i++)
{
int start = i, end = N - 1,
mid, 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 max element
// in the range [i, mid]
// using Segment Tree
int max_element = query(0, N - 1,
i, mid, 0);
// Total sum of subarray after increments
int expected_sum = (mid - i + 1)
* max_element;
// Actual sum of elements
// before increments
int actual_sum = preSum[mid + 1]
- preSum[i];
// Check if such increment is possible
// If true, then current i
// is the actual starting point
// of the required longest subarray
if (expected_sum - actual_sum <= K)
{
// Now for finding the endpoint
// for this range
// Perform the Binary search again
// with the updated start
start = mid + 1;
// Store max end point for the range
// to give longest subarray
max_index = Math.max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else
{
// Perform the Binary Search again
// with the updated end
end = mid - 1;
}
}
// Store the length of longest subarray
res = Math.max(res, max_index - i + 1);
}
// Return result
return res;
}
// Driver code
public static void main (String[] args)
{
int arr[] = { 2, 0, 4, 6, 7 }, K = 6;
int N = arr.length;
System.out.println(longestSubArray(arr, N, K));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 program to find the length of # Longest Subarray with same elements # in atmost K increments # Initialize array for segment tree segment_tree = [0]*(4 * 1000000); # Function that builds the segment # tree to return the max element # in a range def build(A, start, end, node) : if (start == end) : # update the value in segment # tree from given array segment_tree[node] = A[start]; else : # find the middle index mid = (start + end) // 2; # If there are more than one # elements, then recur for left # and right subtrees and # store the max of values in this node segment_tree[node] = max( build(A, start, mid, 2 * node + 1), build(A, mid + 1, end, 2 * node + 2)); return segment_tree[node]; # Function to return the max # element in the given range def query(start, end, l, r, node) : # If the range is out of bounds, # return -1 if (start > r or end < l) : return -1; if (start >= l and end <= r) : return segment_tree[node]; mid = (start + end) // 2; return max(query(start, mid, l, r, 2 * node + 1), query(mid + 1, end, l, r, 2 * node + 2)); # Function that returns length of longest # subarray with same elements in atmost # K increments. def longestSubArray(A, N, K) : # Initialize the result variable # Even though the K is 0, # the required longest subarray, # in that case, will also be of length 1 res = 1; # Initialize the prefix sum array preSum = [0] * (N + 1); # Build the prefix sum array preSum[0] = A[0]; for i in range(N) : preSum[i + 1] = preSum[i] + A[i]; # Build the segment tree # for range max query build(A, 0, N - 1, 0); # Loop through the array # with a starting point as i # for the required subarray till # the longest subarray is found for i in range(N) : start = i; end = N - 1; 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 max element # in the range [i, mid] # using Segment Tree max_element = query(0, N - 1, i, mid, 0); # Total sum of subarray after increments expected_sum = (mid - i + 1) * max_element; # Actual sum of elements # before increments actual_sum = preSum[mid + 1] - preSum[i]; # Check if such increment is possible # If true, then current i # is the actual starting point # of the required longest subarray if (expected_sum - actual_sum <= K) : # Now for finding the endpoint # for this range # Perform the Binary search again # with the updated start start = mid + 1; # Store max end point for the range # to give longest subarray max_index = max(max_index, mid); # If false, it means that # the selected range is invalid else : # Perform the Binary Search again # with the updated end end = mid - 1; # Store the length of longest subarray res = max(res, max_index - i + 1); # Return result return res; # Driver code if __name__ == "__main__" : arr = [ 2, 0, 4, 6, 7 ]; K = 6; N = len(arr); print(longestSubArray(arr, N, K)); # This code is contributed by AnkitRai01
C#
// C# program to find the length of
// longest Subarray with same elements
// in atmost K increments
using System;
class GFG
{
// Initialize array for segment tree
static int []segment_tree = new int[4 * 1000000];
// Function that builds the segment
// tree to return the max element
// in a range
static int build(int []A, int start, int end,
int node)
{
if (start == end)
// update the value in segment
// tree from given array
segment_tree[node] = A[start];
else
{
// find the middle index
int mid = (start + end) / 2;
// If there are more than one
// elements, then recur for left
// and right subtrees and
// store the max of values in this node
segment_tree[node] = Math.Max(
build(A, start, mid, 2 * node + 1),
build(A, mid + 1, end, 2 * node + 2));
}
return segment_tree[node];
}
// Function to return the max
// element in the given range
static int query(int start, int end, int l, int r,
int node)
{
// If the range is out of bounds,
// return -1
if (start > r || end < l)
return -1;
if (start >= l && end <= r)
return segment_tree[node];
int mid = (start + end) / 2;
return Math.Max(query(start, mid, l,
r, 2 * node + 1),
query(mid + 1, end, l,
r, 2 * node + 2));
}
// Function that returns length of longest
// subarray with same elements in atmost
// K increments.
static int longestSubArray(int []A, int N, int K)
{
// Initialize the result variable
// Even though the K is 0,
// the required longest subarray,
// in that case, will also be of length 1
int res = 1;
// Initialize the prefix sum array
int []preSum = new int[N + 1];
// Build the prefix sum array
preSum[0] = A[0];
for (int i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
// Build the segment tree
// for range max query
build(A, 0, N - 1, 0);
// Loop through the array
// with a starting point as i
// for the required subarray till
// the longest subarray is found
for (int i = 0; i < N; i++)
{
int start = i, end = N - 1,
mid, 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 max element
// in the range [i, mid]
// using Segment Tree
int max_element = query(0, N - 1,
i, mid, 0);
// Total sum of subarray after increments
int expected_sum = (mid - i + 1)
* max_element;
// Actual sum of elements
// before increments
int actual_sum = preSum[mid + 1]
- preSum[i];
// Check if such increment is possible
// If true, then current i
// is the actual starting point
// of the required longest subarray
if (expected_sum - actual_sum <= K)
{
// Now for finding the endpoint
// for this range
// Perform the Binary search again
// with the updated start
start = mid + 1;
// Store max end point for the range
// to give longest subarray
max_index = Math.Max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else
{
// Perform the Binary Search again
// with the updated end
end = mid - 1;
}
}
// Store the length of longest subarray
res = Math.Max(res, max_index - i + 1);
}
// Return result
return res;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 2, 0, 4, 6, 7 };
int K = 6;
int N = arr.Length;
Console.WriteLine(longestSubArray(arr, N, K));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find the length of
// Longest Subarray with same elements
// in atmost K increments
// Initialize array for segment tree
let segment_tree = new Array(4 * 1000000);
// Function that builds the segment
// tree to return the max element
// in a range
function build(A, start, end, node)
{
if (start == end)
// update the value in segment
// tree from given array
segment_tree[node] = A[start];
else
{
// find the middle index
let mid = parseInt((start + end) / 2, 10);
// If there are more than one
// elements, then recur for left
// and right subtrees and
// store the max of values in this node
segment_tree[node] = Math.max(
build(A, start, mid, 2 * node + 1),
build(A, mid + 1, end, 2 * node + 2));
}
return segment_tree[node];
}
// Function to return the max
// element in the given range
function query(start, end, l, r, node)
{
// If the range is out of bounds,
// return -1
if (start > r || end < l)
return -1;
if (start >= l && end <= r)
return segment_tree[node];
let mid = parseInt((start + end) / 2, 10);
return Math.max(query(start, mid, l,
r, 2 * node + 1),
query(mid + 1, end, l,
r, 2 * node + 2));
}
// Function that returns length of longest
// subarray with same elements in atmost
// K increments.
function longestSubArray(A, N, K)
{
// Initialize the result variable
// Even though the K is 0,
// the required longest subarray,
// in that case, will also be of length 1
let res = 1;
// Initialize the prefix sum array
let preSum = new Array(N + 1);
// Build the prefix sum array
preSum[0] = A[0];
for (let i = 0; i < N; i++)
preSum[i + 1] = preSum[i] + A[i];
// Build the segment tree
// for range max query
build(A, 0, N - 1, 0);
// Loop through the array
// with a starting point as i
// for the required subarray till
// the longest subarray is found
for (let i = 0; i < N; i++)
{
let start = i, end = N - 1, mid, 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 = parseInt((start + end) / 2, 10);
// Find the max element
// in the range [i, mid]
// using Segment Tree
let max_element = query(0, N - 1, i, mid, 0);
// Total sum of subarray after increments
let expected_sum = (mid - i + 1) * max_element;
// Actual sum of elements
// before increments
let actual_sum = preSum[mid + 1] - preSum[i];
// Check if such increment is possible
// If true, then current i
// is the actual starting point
// of the required longest subarray
if (expected_sum - actual_sum <= K)
{
// Now for finding the endpoint
// for this range
// Perform the Binary search again
// with the updated start
start = mid + 1;
// Store max end point for the range
// to give longest subarray
max_index = Math.max(max_index, mid);
}
// If false, it means that
// the selected range is invalid
else
{
// Perform the Binary Search again
// with the updated end
end = mid - 1;
}
}
// Store the length of longest subarray
res = Math.max(res, max_index - i + 1);
}
// Return result
return res;
}
let arr = [ 2, 0, 4, 6, 7 ], K = 6;
let N = arr.length;
document.write(longestSubArray(arr, N, K));
</script>
Producción:
3
Complejidad de tiempo: O(N*(log(N)) 2 )
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA