Subarreglo más largo que tiene una suma de elementos como máximo ‘k’

Dado un arreglo de enteros, nuestro objetivo es encontrar la longitud del subarreglo más grande que tenga la suma de sus elementos como máximo ‘k’ donde k>0.

Ejemplos: 

Input : arr[] = {1, 2, 1, 0, 1, 1, 0}, k = 4
Output : 5
Explanation:
 {1, 2, 1} => sum = 4, length = 3
 {1, 2, 1, 0}, {2, 1, 0, 1} => sum = 4, length = 4
 {1, 0, 1, 1, 0} =>5 sum = 3, length = 5

Método 1 (Fuerza bruta): Encuentre todos los subarreglos cuya suma sea menor o igual a k y devuelva el de mayor longitud. 
Complejidad de tiempo: O (n ^ 2) 

Método 2 (Eficiente): Un enfoque eficiente es utilizar la técnica de la ventana deslizante . 

1. Recorra la array y verifique si al agregar el elemento actual, su suma es menor o igual que k.
2. Si es menor que k, agréguelo a la suma y aumente la cuenta.
3. Lleve un registro del conteo máximo.

Implementación:

// A C++ program to find longest subarray with
// sum of elements at-least k.
#include <bits/stdc++.h>
using namespace std;
 
// function to find the length of largest subarray
// having sum atmost k.
int atMostSum(int arr[], int n, int k)
{
    int sum = 0;
    int cnt = 0, maxcnt = 0;
 
    for (int i = 0; i < n; i++) {
         
        // If adding current element doesn't
        // cross limit add it to current window
        if ((sum + arr[i]) <= k) {
            sum += arr[i];
            cnt++;
        }
 
        // Else, remove first element of current
        // window and add the current element
        else if(sum!=0)
        {
            sum = sum - arr[i - cnt] + arr[i];
        }
 
        // keep track of max length.
        maxcnt = max(cnt, maxcnt);
    }
    return maxcnt;
}
 
// Driver function
int main()
{
    int arr[] = {1, 2, 1, 0, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
 
    cout << atMostSum(arr, n, k);
    return 0;
}

// Java program to find longest subarray with
// sum of elements at-least k.
import java.util.*;
 
class GFG {
     
    // function to find the length of largest
    // subarray having sum atmost k.
    public static int atMostSum(int arr[], int n,
                                        int k)
    {
        int sum = 0;
        int cnt = 0, maxcnt = 0;
     
        for (int i = 0; i < n; i++) {
             
            // If adding current element doesn't
            // cross limit add it to current window
            if ((sum + arr[i]) <= k) {
                sum += arr[i];
                cnt++;
            }
     
            // Else, remove first element of current
            // window.
            else if(sum!=0)
           {
            sum = sum - arr[i - cnt] + arr[i];
           }
     
            // keep track of max length.
            maxcnt = Math.max(cnt, maxcnt);
        }
        return maxcnt;
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
        int arr[] = { 1, 2, 1, 0, 1, 1, 0 };
        int n = arr.length;
        int k = 4;
     
        System.out.print(atMostSum(arr, n, k));
             
    }
}
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to find longest subarray
# with sum of elements at-least k.
 
# function to find the length of largest
# subarray having sum atmost k.
def atMostSum(arr, n, k):
    _sum = 0
    cnt = 0
    maxcnt = 0
     
    for i in range(n):
 
        # If adding current element doesn't
        # Cross limit add it to current window
        if ((_sum + arr[i]) <= k):
            _sum += arr[i]
            cnt += 1
         
        # Else, remove first element of current
        # window and add the current element
        else if(sum != 0):
            _sum = _sum - arr[i - cnt] + arr[i]
         
        # keep track of max length.
        maxcnt = max(cnt, maxcnt)
 
    return maxcnt
     
# Driver function
arr = [1, 2, 1, 0, 1, 1, 0]
n = len(arr)
k = 4
print(atMostSum(arr, n, k))
 
# This code is contributed by "Abhishek Sharma 44"

// C# program to find longest subarray
// with sum of elements at-least k.
using System;
 
class GFG {
     
    // function to find the length of largest
    // subarray having sum atmost k.
    public static int atMostSum(int []arr, int n,
                                           int k)
    {
        int sum = 0;
        int cnt = 0, maxcnt = 0;
     
        for (int i = 0; i < n; i++) {
             
            // If adding current element doesn't
            // cross limit add it to current window
            if ((sum + arr[i]) <= k) {
                sum += arr[i];
                cnt++;
            }
     
            // Else, remove first element
            // of current window.
            else if(sum!=0)
            {
                sum = sum - arr[i - cnt] + arr[i];
            }
     
            // keep track of max length.
            maxcnt = Math.Max(cnt, maxcnt);
        }
        return maxcnt;
    }
     
    // Driver Code
    public static void Main()
    {
        int []arr = {1, 2, 1, 0, 1, 1, 0};
        int n = arr.Length;
        int k = 4;
     
        Console.Write(atMostSum(arr, n, k));
             
    }
}
 
// This code is contributed by Nitin Mittal

<?php
// A PHP program to find longest
// subarray with sum of elements
// at-least k.
 
// function to find the length
// of largest subarray having
// sum atmost k.
function atMostSum(&$arr, $n, $k)
{
    $sum = 0;
    $cnt = 0;
    $maxcnt = 0;
 
    for($i = 0; $i < $n; $i++)
    {
        // If adding current element
        // doesn't cross limit add
        // it to current window
        if (($sum + $arr[$i]) <= $k)
        {
            $sum += $arr[$i] ;
            $cnt += 1 ;
        }
 
        // Else, remove first element
        // of current window and add
        // the current element
        else if($sum != 0)
            $sum = $sum - $arr[$i - $cnt] +
                               $arr[$i];
         
        // keep track of max length.
        $maxcnt = max($cnt, $maxcnt);
    }
    return $maxcnt;
}
 
// Driver Code
$arr = array(1, 2, 1, 0, 1, 1, 0);
$n = sizeof($arr);
$k = 4;
 
print(atMostSum($arr, $n, $k));
 
// This code is contributed
// by ChitraNayal
?>

<script>
// A Javascript program to find longest subarray with
// sum of elements at-least k.
 
// function to find the length of largest subarray
// having sum atmost k.
function atMostSum(arr, n, k)
{
    let sum = 0;
    let cnt = 0, maxcnt = 0;
 
    for (let i = 0; i < n; i++) {
         
        // If adding current element doesn't
        // cross limit add it to current window
        if ((sum + arr[i]) <= k) {
            sum += arr[i];
            cnt++;
        }
 
        // Else, remove first element of current
        // window and add the current element
        else if(sum!=0)
        {
            sum = sum - arr[i - cnt] + arr[i];
        }
 
        // keep track of max length.
        maxcnt = Math.max(cnt, maxcnt);
    }
    return maxcnt;
}
 
// Driver function
    let arr = [1, 2, 1, 0, 1, 1, 0];
    let n = arr.length;
    let k = 4;
 
    document.write(atMostSum(arr, n, k));
 
</script>

5

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.

Este artículo es una contribución de Kshitiz gupta . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.