Dado un arreglo arr[] y dos enteros K y X , la tarea es encontrar la suma máxima entre todos los subarreglos de tamaño K con la suma menor que X .
Ejemplos:
Entrada: arr[] = {20, 2, 3, 10, 5}, K = 3, X = 20
Salida: 18
Explicación: el subarreglo de tamaño 3 que tiene una suma máxima menor que 20 es {3, 10, 5}. Por lo tanto, la salida requerida es 18.Entrada: arr[] = {-5, 8, 7, 2, 10, 1, 20, -4, 6, 9}, K = 5, X = 30 Salida: 29 Explicación: Subarreglo de tamaño 5 con
suma máxima
menor que 30 es {2, 10, 1, 20, -4}. Por lo tanto, la salida requerida es 29.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos de tamaño K y verificar si su suma es menor que X o no. Imprime la suma máxima obtenida entre todos esos subarreglos.
Complejidad temporal: O(N * K)
Espacio auxiliar: O(1)
Enfoque eficiente: siga los pasos a continuación para resolver el problema utilizando la técnica de ventana deslizante :
- Inicialice una variable sum_K para almacenar la suma de los primeros elementos de la array K.
- Si sum_K es menor que X , entonces inicialice Max_Sum con sum_K .
- Atraviese la array desde (K + 1) el índice y realice lo siguiente:
- En cada iteración, reste el primer elemento del subarreglo de longitud K anterior y agregue el elemento actual a sum_K .
- Si sum_K es menor que X , compare sum_K con Max_Sum y actualice Max_Sum en consecuencia.
- Finalmente, imprima Max_Sum .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum sum
// among all subarrays of size K
// with the sum less than X
void maxSumSubarr(int A[], int N,
int K, int X)
{
// Initialize sum_K to 0
int sum_K = 0;
// Calculate sum of first K elements
for (int i = 0; i < K; i++) {
sum_K += A[i];
}
int Max_Sum = 0;
// If sum_K is less than X
if (sum_K < X) {
// Initialize MaxSum with sum_K
Max_Sum = sum_K;
}
// Iterate over the array from
// (K + 1)-th index
for (int i = K; i < N; i++) {
// Subtract the first element
// from the previous K elements
// and add the next element
sum_K -= (A[i - K] - A[i]);
// If sum_K is less than X
if (sum_K < X) {
// Update the Max_Sum
Max_Sum = max(Max_Sum, sum_K);
}
}
cout << Max_Sum << endl;
}
// Driver Code
int main()
{
int arr[] = { -5, 8, 7, 2, 10,
1, 20, -4, 6, 9 };
int K = 5;
int X = 30;
// Size of Array
int N = sizeof(arr)
/ sizeof(arr[0]);
// Function Call
maxSumSubarr(arr, N, K, X);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to calculate maximum sum
// among all subarrays of size K
// with the sum less than X
private static void maxSumSubarr(int A[], int N,
int K, int X)
{
// Initialize sum_K to 0
int sum_K = 0;
// Calculate sum of first K elements
for(int i = 0; i < K; i++)
{
sum_K += A[i];
}
int Max_Sum = 0;
// If sum_K is less than X
if (sum_K < X)
{
// Initialize MaxSum with sum_K
Max_Sum = sum_K;
}
// Iterate over the array from
// (K + 1)-th index
for(int i = K; i < N; i++)
{
// Subtract the first element
// from the previous K elements
// and add the next element
sum_K -= (A[i - K] - A[i]);
// If sum_K is less than X
if (sum_K < X)
{
// Update the Max_Sum
Max_Sum = Math.max(Max_Sum, sum_K);
}
}
System.out.println(Max_Sum);
}
// Driver Code
public static void main (String[] args)
{
int arr[] = { -5, 8, 7, 2, 10,
1, 20, -4, 6, 9 };
int K = 5;
int X = 30;
// Size of Array
int N = arr.length;
// Function Call
maxSumSubarr(arr, N, K, X);
}
}
// This code is contributed by jithin
Python3
# Python3 program for the above approach # Function to calculate maximum sum # among all subarrays of size K # with the sum less than X def maxSumSubarr(A, N, K, X): # Initialize sum_K to 0 sum_K = 0 # Calculate sum of first K elements for i in range(0, K): sum_K += A[i] Max_Sum = 0 # If sum_K is less than X if (sum_K < X): # Initialize MaxSum with sum_K Max_Sum = sum_K # Iterate over the array from # (K + 1)-th index for i in range(K, N): # Subtract the first element # from the previous K elements # and add the next element sum_K -= (A[i - K] - A[i]) # If sum_K is less than X if (sum_K < X): # Update the Max_Sum Max_Sum = max(Max_Sum, sum_K) print(Max_Sum) # Driver Code arr = [ -5, 8, 7, 2, 10, 1, 20, -4, 6, 9 ] K = 5 X = 30 # Size of Array N = len(arr) # Function Call maxSumSubarr(arr, N, K, X) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate maximum sum
// among all subarrays of size K
// with the sum less than X
private static void maxSumSubarr(int []A, int N,
int K, int X)
{
// Initialize sum_K to 0
int sum_K = 0;
// Calculate sum of first K elements
for(int i = 0; i < K; i++)
{
sum_K += A[i];
}
int Max_Sum = 0;
// If sum_K is less than X
if (sum_K < X)
{
// Initialize MaxSum with sum_K
Max_Sum = sum_K;
}
// Iterate over the array from
// (K + 1)-th index
for(int i = K; i < N; i++)
{
// Subtract the first element
// from the previous K elements
// and add the next element
sum_K -= (A[i - K] - A[i]);
// If sum_K is less than X
if (sum_K < X)
{
// Update the Max_Sum
Max_Sum = Math.Max(Max_Sum, sum_K);
}
}
Console.WriteLine(Max_Sum);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { -5, 8, 7, 2, 10,
1, 20, -4, 6, 9 };
int K = 5;
int X = 30;
// Size of Array
int N = arr.Length;
// Function Call
maxSumSubarr(arr, N, K, X);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// JavaScript program to implement the above approach
// Function to calculate maximum sum
// among all subarrays of size K
// with the sum less than X
function maxSumSubarr(A, N, K, X)
{
// Initialize sum_K to 0
let sum_K = 0;
// Calculate sum of first K elements
for (let i = 0; i < K; i++) {
sum_K += A[i];
}
let Max_Sum = 0;
// If sum_K is less than X
if (sum_K < X) {
// Initialize MaxSum with sum_K
Max_Sum = sum_K;
}
// Iterate over the array from
// (K + 1)-th index
for (let i = K; i < N; i++) {
// Subtract the first element
// from the previous K elements
// and add the next element
sum_K -= (A[i - K] - A[i]);
// If sum_K is less than X
if (sum_K < X) {
// Update the Max_Sum
Max_Sum = Math.max(Max_Sum, sum_K);
}
}
document.write(Max_Sum);
}
// Driver Code
let arr = [ -5, 8, 7, 2, 10,
1, 20, -4, 6, 9 ];
let K = 5;
let X = 30;
// Size of Array
let N = arr.length;
// Function Call
maxSumSubarr(arr, N, K, X);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción:
29
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por supratik_mitra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA