Tamaño máximo del subarreglo, de modo que todos los subarreglos de ese tamaño tengan una suma menor que k

Dado un arreglo de n enteros positivos y un entero positivo k , la tarea es encontrar el tamaño máximo del subarreglo tal que todos los subarreglos de ese tamaño tengan la suma de elementos menor o igual a k.

Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4} y k = 8.
Salida: 2
Suma de subarreglos de tamaño 1: 1, 2, 3, 4.
Suma de subarreglos de tamaño 2: 3, 5, 7 Suma de
subarreglos de tamaño 3: 6, 9.
Suma de subarreglos de tamaño 4: 10.
Entonces, el tamaño máximo de subarreglo tal que todos los subarreglos de ese tamaño tienen la suma de elementos menor que 8 es 2.

Entrada: arr[] = {1, 2, 10, 4} y k = 8.
Salida: -1
Hay un elemento de array con un valor mayor que k, por lo que la suma de subarreglo no puede ser menor que k.

Entrada: arr[] = {1, 2, 10, 4} y K = 14
Salida: 2

Enfoque ingenuo: en primer lugar, el tamaño de subarreglo requerido debe estar entre 1 y n . Ahora, dado que todos los elementos del arreglo son enteros positivos, podemos decir que la suma del prefijo de cualquier subarreglo será estrictamente creciente. Así, podemos decir que 

if arr[i] + arr[i + 1] + ..... + arr[j - 1] + arr[j] <= K
then arr[i] + arr[i + 1] + ..... + arr[j - 1] <= K, as arr[j] is a positive integer.
  • Realice una búsqueda binaria en el rango de 1 an y encuentre el tamaño de subarreglo más alto de modo que todos los subarreglos de ese tamaño tengan la suma de elementos menor o igual a k.

Implementación:

C++

// C++ program to find maximum 
// subarray size, such that all 
// subarrays of that size have 
// sum less than K.
#include<bits/stdc++.h>
using namespace std;
  
// Search for the maximum length of 
// required subarray.
int bsearch(int prefixsum[], int n, 
                             int k)
{
    // Initialize result
    int ans = -1; 
  
    // Do Binary Search for largest 
    // subarray size 
    int left = 1, right = n;
    while (left <= right)
    {
        int mid = (left + right) / 2;
  
        // Check for all subarrays after mid
        int i;
        for (i = mid; i <= n; i++)
        {
            // Checking if all the subarrays
            //  of a size less than k.
            if (prefixsum[i] - prefixsum[i - mid] > k)
                break;
        }
  
        // All subarrays of size mid have 
        // sum less than or equal to k
        if (i == n + 1)
        {
            left = mid + 1;
            ans = mid;
        }
  
        // We found a subarray of size mid 
        // with sum greater than k
        else
            right = mid - 1;
    }
    return ans;
}
  
// Return the maximum subarray size,
// such that all subarray of that size
// have sum less than K.
int maxSize(int arr[], int n, int k)
{
    // Initialize prefix sum array as 0.
    int prefixsum[n + 1];
    memset(prefixsum, 0, sizeof(prefixsum));
  
    // Finding prefix sum of the array.
    for (int i = 0; i < n; i++)
        prefixsum[i + 1] = prefixsum[i] + 
                           arr[i];
  
    return bsearch(prefixsum, n, k);
}
  
// Driver code
int main()
{
    int arr[] = {1, 2, 10, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 14;
    cout << maxSize(arr, n, k) << endl;
    return 0;
}

Java

// Java program to find maximum 
// subarray size, such that all 
// subarrays of that size have
// sum less than K.
import java.util.Arrays;
  
class GFG 
{
      
    // Search for the maximum length 
    // of required subarray.
    static int bsearch(int prefixsum[], 
                       int n, int k)
    {
        // Initialize result
        int ans = -1; 
  
        // Do Binary Search for largest 
        // subarray size
        int left = 1, right = n;
          
        while (left <= right) 
        {
            int mid = (left + right) / 2;
  
            // Check for all subarrays after mid
            int i;
            for (i = mid; i <= n; i++) 
            {
                  
                // Checking if all the subarrays 
                // of a size is less than k.
                if (prefixsum[i] - prefixsum[i - mid] > k)
                    break;
            }
  
            // All subarrays of size mid have 
            // sum less than or equal to k
            if (i == n + 1)
            {
                left = mid + 1;
                ans = mid;
            }
  
            // We found a subarray of size mid 
            // with sum greater than k
            else
                right = mid - 1;
        }
  
        return ans;
    }
  
    // Return the maximum subarray size, such 
    // that all subarray of that size have 
    // sum less than K.
    static int maxSize(int arr[], int n, int k)
    {
          
        // Initialize prefix sum array as 0.
        int prefixsum[] = new int[n + 1];
        Arrays.fill(prefixsum, 0);
  
        // Finding prefix sum of the array.
        for (int i = 0; i < n; i++)
            prefixsum[i + 1] = prefixsum[i] + arr[i];
  
        return bsearch(prefixsum, n, k);
    }
      
    // Driver code
    public static void main(String arg[])
    {
        int arr[] = { 1, 2, 10, 4 };
        int n = arr.length;
        int k = 14;
        System.out.println(maxSize(arr, n, k));
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to find maximum 
# subarray size, such that all 
# subarrays of that size have
# sum less than K.
  
# Search for the maximum length of 
# required subarray.
def bsearch(prefixsum, n, k):
  
    # Initialize result
    # Do Binary Search for largest
    # subarray size
    ans, left, right = -1, 1, n
  
    while (left <= right):
  
        # Check for all subarrays after mid
        mid = (left + right)//2
  
        for i in range(mid, n + 1):
  
            # Checking if all the subarray of 
            # a size is less than k.
            if (prefixsum[i] - prefixsum[i - mid] > k):
                i = i - 1
                break
        i = i + 1
        if (i == n + 1):
            left = mid + 1
            ans = mid
        # We found a subarray of size mid with sum
        # greater than k
        else:
            right = mid - 1
  
    return ans;
  
# Return the maximum subarray size, such 
# that all subarray of that size have 
# sum less than K.
def maxSize(arr, n, k):
    prefixsum = [0 for x in range(n + 1)]
      
    # Finding prefix sum of the array.
    for i in range(n):
        prefixsum[i + 1] = prefixsum[i] + arr[i]
  
    return bsearch(prefixsum, n, k);
  
# Driver Code
arr = [ 1, 2, 10, 4 ]
n = len(arr)
k = 14
print (maxSize(arr, n, k))
  
# This code is contributed by Afzal

C#

// C# program to find maximum 
// subarray size, such that all 
// subarrays of that size have
// sum less than K.
using System;
  
class GFG {
      
    // Search for the maximum length 
    // of required subarray.
    static int bsearch(int []prefixsum, 
                          int n, int k)
    {
          
        // Initialize result
        int ans = -1; 
  
        // Do Binary Search for 
        // largest subarray size
        int left = 1, right = n;
          
        while (left <= right) 
        {
            int mid = (left + right) / 2;
  
            // Check for all subarrays 
            // after mid
            int i;
            for (i = mid; i <= n; i++) 
            {
                  
                // Checking if all the 
                // subarrays of a size is
                // less than k.
                if (prefixsum[i] - 
                     prefixsum[i - mid] > k)
                    break;
            }
  
            // All subarrays of size mid have 
            // sum less than or equal to k
            if (i == n + 1)
            {
                left = mid + 1;
                ans = mid;
            }
  
            // We found a subarray of size mid 
            // with sum greater than k
            else
                right = mid - 1;
        }
  
        return ans;
    }
  
    // Return the maximum subarray size, such 
    // that all subarray of that size have 
    // sum less than K.
    static int maxSize(int []arr, int n, int k)
    {
          
        // Initialize prefix sum array as 0.
        int []prefixsum = new int[n + 1];
        for(int i=0;i<n+1;i++)
        prefixsum[i]=0;
          
  
        // Finding prefix sum of the array.
        for (int i = 0; i < n; i++)
            prefixsum[i + 1] = prefixsum[i]
                                     + arr[i];
  
        return bsearch(prefixsum, n, k);
    }
      
    // Driver code
    public static void Main()
    {
        int []arr = { 1, 2, 10, 4 };
        int n = arr.Length;
        int k = 14;
          
        Console.Write(maxSize(arr, n, k));
    }
}
  
// This code is contributed by nitin mittal.

PHP

<?php 
// PHP program to find maximum subarray 
// size, such that all subarrays of that 
// size have sum less than K.
  
// Search for the maximum length of 
// required subarray.
function bsearch(&$prefixsum, $n, $k)
{
    // Initialize result
    $ans = -1; 
  
    // Do Binary Search for largest 
    // subarray size 
    $left = 1;
    $right = $n;
    while ($left <= $right)
    {
        $mid = intval(($left + $right) / 2);
  
        // Check for all subarrays after mid
        for ($i = $mid; $i <= $n; $i++)
        {
            // Checking if all the subarrays
            // of a size less than k.
            if ($prefixsum[$i] - $prefixsum[$i - 
                                 $mid] > $k)
                break;
        }
  
        // All subarrays of size mid have 
        // sum less than or equal to k
        if ($i == $n + 1)
        {
            $left = $mid + 1;
            $ans = $mid;
        }
  
        // We found a subarray of size mid 
        // with sum greater than k
        else
            $right = $mid - 1;
    }
    return $ans;
}
  
// Return the maximum subarray size,
// such that all subarray of that size
// have sum less than K.
function maxSize(&$arr, $n, $k)
{
    // Initialize prefix sum array as 0.
    $prefixsum = array_fill(0, $n + 1, NULL);
  
    // Finding prefix sum of the array.
    for ($i = 0; $i < $n; $i++)
        $prefixsum[$i + 1] = $prefixsum[$i] + 
                             $arr[$i];
  
    return bsearch($prefixsum, $n, $k);
}
  
// Driver code
$arr = array(1, 2, 10, 4);
$n = sizeof($arr);
$k = 14;
echo maxSize($arr, $n, $k) . "\n";
  
// This code is contributed 
// by ChitraNayal
?>

Javascript

<script>
  
// javascript program to find maximum 
// subarray size, such that all 
// subarrays of that size have
// sum less than K.
  
    // Search for the maximum length
    // of required subarray.
    function bsearch(prefixsum , n , k) 
    {
        // Initialize result
        var ans = -1;
  
        // Do Binary Search for largest
        // subarray size
        var left = 1, right = n;
  
        while (left <= right) {
            var mid = parseInt((left + right) / 2);
  
            // Check for all subarrays after mid
            var i;
            for (i = mid; i <= n; i++) {
  
                // Checking if all the subarrays
                // of a size is less than k.
                if (prefixsum[i] - prefixsum[i - mid] > k)
                    break;
            }
  
            // All subarrays of size mid have
            // sum less than or equal to k
            if (i == n + 1) {
                left = mid + 1;
                ans = mid;
            }
  
            // We found a subarray of size mid
            // with sum greater than k
            else
                right = mid - 1;
        }
  
        return ans;
    }
  
    // Return the maximum subarray size, such
    // that all subarray of that size have
    // sum less than K.
    function maxSize(arr , n , k) {
  
        // Initialize prefix sum array as 0.
        var prefixsum = Array(n + 1).fill(0);
      
        // Finding prefix sum of the array.
        for (i = 0; i < n; i++)
            prefixsum[i + 1] = prefixsum[i] + arr[i];
  
        return bsearch(prefixsum, n, k);
    }
  
    // Driver code
        var arr = [ 1, 2, 10, 4 ];
        var n = arr.length;
        var k = 14;
        document.write(maxSize(arr, n, k));
  
// This code contributed by Rajput-Ji
  
</script>
Producción

2

Complejidad de tiempo: O(n log n) , donde N representa el tamaño de la array dada.
Espacio auxiliar: O(n) , donde N representa el tamaño de la array dada.

Enfoque eficiente: este método utiliza la técnica de la ventana deslizante para resolver el problema dado. 

  • El enfoque es encontrar el tamaño mínimo del subarreglo cuya suma sea mayor que el entero k.
  • Aumente el tamaño de la ventana desde el extremo hasta el cual la suma de esa ventana es mayor que k.
  • Ahora, almacene ese tamaño de subarreglo si es más pequeño que el tamaño de subarreglo ya almacenado (en ans variable).
  • Ahora, disminuya el tamaño del subarreglo desde el principio. La variable ans almacenará el tamaño mínimo del subarreglo cuya suma sea mayor que k.
  • Por fin, (respuesta-1) es la respuesta real. Entonces, ese tamaño de subarreglo – 1 es el tamaño máximo de subarreglo, de modo que todos los subarreglo de ese tamaño tendrán una suma menor o igual a k.

Implementación:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the 
// largest size subarray
void func(vector<int> arr, 
          int k, int n)
{
    // Variable declaration
    int ans = n;
    int sum = 0;
    int start = 0;
  
    // Loop till N
    for (int end = 0; end < n; end++)
    {
        // Sliding window from left
        sum += arr[end];
  
        while (sum > k) {
            // Sliding window from right
            sum -= arr[start];
            start++;
  
            // Storing sub-array size - 1
            // for which sum was greater than k
            ans = min(ans, end - start + 1);
  
            // Sum will be 0 if start>end
            // because all elements are positive
            // start>end only when arr[end]>k i.e,
            // there is an array element with
            // value greater than k, so sub-array
            // sum cannot be less than k.
            if (sum == 0)
                break;
        }
        if (sum == 0) {
            ans = -1;
            break;
        }
    }
  
    // Print the answer
    cout << ans;
}
  
// Driver code
int main()
{
    vector<int> arr{ 1, 2, 3, 4 };
    int k = 8;
    int n = arr.size();
  
    // Function call
    func(arr, k, n);
  
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
  
class GFG{
      
// Function to find the 
// largest size subarray
public static void func(int arr[], 
                        int k, int n)
{
      
    // Variable declaration
    int ans = n;
    int sum = 0;
    int start = 0;
      
    // Loop till N
    for(int end = 0; end < n; end++)
    {
          
        // Sliding window from left
        sum += (int)arr[end];
          
        while (sum > k) 
        {
              
            // Sliding window from right
            sum -= (int)arr[start];
            start++;
  
            // Storing sub-array size - 1
            // for which sum was greater than k
            ans = Math.min(ans, end - start + 1);
  
            // Sum will be 0 if start>end
            // because all elements are positive
            // start>end only when arr[end]>k i.e,
            // there is an array element with
            // value greater than k, so sub-array
            // sum cannot be less than k.
            if (sum == 0)
                break;
        }
          
        if (sum == 0) 
        {
            ans = -1;
            break;
        }
    }
      
    // Print the answer
    System.out.println(ans);
}
  
// Driver code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 3, 4 };
    int k = 8;
    int n = arr.length;
      
    // Function call
    func(arr, k, n);
}
}
  
// This code is contributed by rag2127

Python3

# Python3 program for the above approach
  
# Function to find the 
# largest size subarray
def func(arr, k, n):
      
    # Variable declaration
    ans = n
    Sum = 0
    start = 0
  
    # Loop till N
    for end in range(n):
  
        # Sliding window from left
        Sum += arr[end]
  
        while (Sum > k):
              
            # Sliding window from right
            Sum -= arr[start]
            start += 1
  
            # Storing sub-array size - 1
            # for which sum was greater than k
            ans = min(ans, end - start + 1)
  
            # Sum will be 0 if start>end
            # because all elements are positive
            # start>end only when arr[end]>k i.e,
            # there is an array element with
            # value greater than k, so sub-array
            # sum cannot be less than k.
            if (Sum == 0):
                break
                  
        if (Sum == 0):
            ans = -1
            break
              
    # Print the answer
    print(ans)
  
# Driver code
arr = [ 1, 2, 3, 4 ]
k = 8
n = len(arr)
  
# Function call
func(arr, k, n)
  
# This code is contributed by avanitrachhadiya2155

C#

// C# program for the above approach
using System; 
using System.Collections;
  
class GFG{
       
// Function to find the 
// largest size subarray
static void func(ArrayList arr, 
                 int k, int n)
{
      
    // Variable declaration
    int ans = n;
    int sum = 0;
    int start = 0;
   
    // Loop till N
    for(int end = 0; end < n; end++)
    {
          
        // Sliding window from left
        sum += (int)arr[end];
   
        while (sum > k) 
        {
              
            // Sliding window from right
            sum -= (int)arr[start];
            start++;
   
            // Storing sub-array size - 1
            // for which sum was greater than k
            ans = Math.Min(ans, end - start + 1);
   
            // Sum will be 0 if start>end
            // because all elements are positive
            // start>end only when arr[end]>k i.e,
            // there is an array element with
            // value greater than k, so sub-array
            // sum cannot be less than k.
            if (sum == 0)
                break;
        }
        if (sum == 0) 
        {
            ans = -1;
            break;
        }
    }
      
    // Print the answer
    Console.Write(ans);
}
   
// Driver code
public static void Main(string[] args)
{
    ArrayList arr = new ArrayList(){ 1, 2, 3, 4 };
    int k = 8;
    int n = arr.Count;
   
    // Function call
    func(arr, k, n);
}
}
  
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript program for the above approach
  
// Function to find the 
// largest size subarray
function func(arr, k, n)
{
    // Variable declaration
    let ans = n;
    let sum = 0;
    let start = 0;
  
    // Loop till N
    for (let end = 0; end < n; end++)
    {
        // Sliding window from left
        sum += arr[end];
  
        while (sum > k) {
            // Sliding window from right
            sum -= arr[start];
            start++;
  
            // Storing sub-array size - 1
            // for which sum was greater than k
            ans = Math.min(ans, end - start + 1);
  
            // Sum will be 0 if start>end
            // because all elements are positive
            // start>end only when arr[end]>k i.e,
            // there is an array element with
            // value greater than k, so sub-array
            // sum cannot be less than k.
            if (sum == 0)
                break;
        }
        if (sum == 0) {
            ans = -1;
            break;
        }
    }
  
    // Print the answer
    document.write(ans);
}
  
// Driver code
    let arr = [ 1, 2, 3, 4 ];
    let k = 8;
    let n = arr.length;
  
    // Function call
    func(arr, k, n);
      
</script>
Producción

2

Complejidad de tiempo: O(N), donde N representa el tamaño de la array dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 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 *