Dado un arreglo arr[] de N enteros, encuentre la longitud del subarreglo más largo que tenga suma en el rango [L, R] .
Ejemplos:
Entrada: arr[] = {1, 4, 6}, L = 3, R = 8
Salida: 2
Explicación: Los subarreglos válidos con la suma en el rango [3, 8] son {1, 4}, {4}, {6}. El subarreglo más largo entre ellos es {1, 4} que tiene una longitud de 2.Entrada: arr[] = {15, 2, 4, 8, 9, 5, 10, 23}, L = 10, R = 23
Salida: 4
Enfoque: El problema planteado se puede resolver utilizando la técnica de la ventana deslizante . Inicialmente, cree una ventana a partir de los elementos iniciales de la array de modo que su suma sea mayor que L . Mantenga dos variables i y j que representen el índice inicial y final de la ventana actual. Si la suma de la ventana actual es mayor que R , incremente el valor de i y si la suma es menor que L , incremente el valor de j . Para las ventanas con su suma en el rango [L, R] , mantenga su longitud máxima en una variable len , que es la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of
// the longest subarray having its
// sum in the given range [L, R]
int largestSubArraySum(int arr[], int N,
int L, int R)
{
// Store sum of current window
int sum = 0;
// Stores indices of current window
int i = 0, j = 0;
// Stores the maximum length
int len = 0;
// Calculating initial window
while (sum < L && j < N) {
sum += arr[j];
j++;
}
// Loop to iterate over all windows
// of having sum in range [L, R]
while (i < N && j < N) {
// If sum of window is less than L
if (sum < L) {
sum += arr[j];
j++;
}
// If sum of window is more than R
else if (sum > R) {
sum -= arr[i];
i++;
}
// If sum is in the range [L, R]
else {
// Update length
len = max(len, j - i);
sum += arr[j];
j++;
}
}
// Return Answer
return len;
}
// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int N = sizeof(arr) / sizeof(arr[0]);
int L = 10, R = 23;
cout << largestSubArraySum(arr, N, L, R);
return 0;
}
Java
// Java program of the above approach
class GFG {
// Function to find the length of
// the longest subarray having its
// sum in the given range [L, R]
static int largestSubArraySum(int[] arr, int N, int L,
int R)
{
// Store sum of current window
int sum = 0;
// Stores indices of current window
int i = 0, j = 0;
// Stores the maximum length
int len = 0;
// Calculating initial window
while (sum < L && j < N) {
sum += arr[j];
j++;
}
// Loop to iterate over all windows
// of having sum in range [L, R]
while (i < N && j < N) {
// If sum of window is less than L
if (sum < L) {
sum += arr[j];
j++;
}
// If sum of window is more than R
else if (sum > R) {
sum -= arr[i];
i++;
}
// If sum is in the range [L, R]
else {
// Update length
len = Math.max(len, j - i);
sum += arr[j];
j++;
}
}
// Return Answer
return len;
}
// Driver Code
public static void main(String args[])
{
int[] arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
int N = arr.length;
int L = 10, R = 23;
System.out.println(largestSubArraySum(arr, N, L, R));
}
}
// This code is contributed by Saurabh Jaiswal
Python3
# Python 3 program of the above approach # Function to find the length of # the longest subarray having its # sum in the given range [L, R] def largestSubArraySum(arr, N, L, R): # Store sum of current window sum = 0 # Stores indices of current window i = 0 j = 0 # Stores the maximum length len = 0 # Calculating initial window while (sum < L and j < N): sum += arr[j] j += 1 # Loop to iterate over all windows # of having sum in range [L, R] while (i < N and j < N): # If sum of window is less than L if (sum < L): sum += arr[j] j += 1 # If sum of window is more than R elif (sum > R): sum -= arr[i] i += 1 # If sum is in the range [L, R] else: # Update length len = max(len, j - i) sum += arr[j] j += 1 # Return Answer return len # Driver Code if __name__ == "__main__": arr = [15, 2, 4, 8, 9, 5, 10, 23] N = len(arr) L = 10 R = 23 print(largestSubArraySum(arr, N, L, R)) # This code is contributed by gaurav01.
C#
// C# program of the above approach
using System;
class GFG {
// Function to find the length of
// the longest subarray having its
// sum in the given range [L, R]
static int largestSubArraySum(int[] arr, int N, int L,
int R)
{
// Store sum of current window
int sum = 0;
// Stores indices of current window
int i = 0, j = 0;
// Stores the maximum length
int len = 0;
// Calculating initial window
while (sum < L && j < N) {
sum += arr[j];
j++;
}
// Loop to iterate over all windows
// of having sum in range [L, R]
while (i < N && j < N) {
// If sum of window is less than L
if (sum < L) {
sum += arr[j];
j++;
}
// If sum of window is more than R
else if (sum > R) {
sum -= arr[i];
i++;
}
// If sum is in the range [L, R]
else {
// Update length
len = Math.Max(len, j - i);
sum += arr[j];
j++;
}
}
// Return Answer
return len;
}
// Driver Code
public static void Main()
{
int[] arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
int N = arr.Length;
int L = 10, R = 23;
Console.WriteLine(largestSubArraySum(arr, N, L, R));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program of the above approach
// Function to find the length of
// the longest subarray having its
// sum in the given range [L, R]
const largestSubArraySum = (arr, N, L, R) => {
// Store sum of current window
let sum = 0;
// Stores indices of current window
let i = 0, j = 0;
// Stores the maximum length
let len = 0;
// Calculating initial window
while (sum < L && j < N) {
sum += arr[j];
j++;
}
// Loop to iterate over all windows
// of having sum in range [L, R]
while (i < N && j < N) {
// If sum of window is less than L
if (sum < L) {
sum += arr[j];
j++;
}
// If sum of window is more than R
else if (sum > R) {
sum -= arr[i];
i++;
}
// If sum is in the range [L, R]
else {
// Update length
len = Math.max(len, j - i);
sum += arr[j];
j++;
}
}
// Return Answer
return len;
}
// Driver Code
let arr = [15, 2, 4, 8, 9, 5, 10, 23];
let N = arr.length;
let L = 10, R = 23;
document.write(largestSubArraySum(arr, N, L, R));
// This code is contributed by rakeshsahni
</script>
Producción
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)