Longitud del subarreglo más largo con los mismos elementos en incrementos de K como máximo

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:
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:
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: 
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

Deja una respuesta

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