Maximice la longitud del subarreglo más largo que consta de los mismos elementos en un máximo de K decrementos

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:

  1. 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.
  2. 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
       
  3. 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

Deja una respuesta

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