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