Dado un arreglo, encuentra el subarreglo (que contiene al menos k números) que tiene la suma más grande.
Ejemplos:
Input : arr[] = {-4, -2, 1, -3}
k = 2
Output : -1
The sub array is {-2, 1}
Input : arr[] = {1, 1, 1, 1, 1, 1}
k = 2
Output : 6
The sub array is {1, 1, 1, 1, 1, 1}
Preguntado en: Facebook
Este problema es una extensión del problema del subarreglo de suma más grande .
- Primero calculamos la suma máxima hasta cada índice y la almacenamos en una array maxSum[].
- Después de llenar la array, usamos el concepto de ventana deslizante de tamaño k. Mantenga un registro de la suma de los k elementos actuales. Para calcular la suma de la ventana actual, elimine el primer elemento de la ventana anterior y agregue el elemento actual. Después de obtener la suma de la ventana actual, agregamos la suma máxima de la ventana anterior, si es mayor que el máximo actual, de lo contrario no lo actualizamos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find largest subarray sum with
// at-least k elements in it.
#include<bits/stdc++.h>
using namespace std;
// Returns maximum sum of a subarray with at-least
// k elements.
int maxSumWithK(int a[], int n, int k)
{
// maxSum[i] is going to store maximum sum
// till index i such that a[i] is part of the
// sum.
int maxSum[n];
maxSum[0] = a[0];
// We use Kadane's algorithm to fill maxSum[]
// Below code is taken from method 3 of
// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
int curr_max = a[0];
for (int i = 1; i < n; i++)
{
curr_max = max(a[i], curr_max+a[i]);
maxSum[i] = curr_max;
}
// Sum of first k elements
int sum = 0;
for (int i = 0; i < k; i++)
sum += a[i];
// Use the concept of sliding window
int result = sum;
for (int i = k; i < n; i++)
{
// Compute sum of k elements ending
// with a[i].
sum = sum + a[i] - a[i-k];
// Update result if required
result = max(result, sum);
// Include maximum sum till [i-k] also
// if it increases overall max.
result = max(result, sum + maxSum[i-k]);
}
return result;
}
// Driver code
int main()
{
int a[] = {1, 2, 3, -10, -3};
int k = 4;
int n = sizeof(a)/sizeof(a[0]);
cout << maxSumWithK(a, n, k);
return 0;
}
Java
// Java program to find largest subarray sum with
// at-least k elements in it.
class Test
{
// Returns maximum sum of a subarray with at-least
// k elements.
static int maxSumWithK(int a[], int n, int k)
{
// maxSum[i] is going to store maximum sum
// till index i such that a[i] is part of the
// sum.
int maxSum[] = new int [n];
maxSum[0] = a[0];
// We use Kadane's algorithm to fill maxSum[]
// Below code is taken from method 3 of
// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
int curr_max = a[0];
for (int i = 1; i < n; i++)
{
curr_max = Math.max(a[i], curr_max+a[i]);
maxSum[i] = curr_max;
}
// Sum of first k elements
int sum = 0;
for (int i = 0; i < k; i++)
sum += a[i];
// Use the concept of sliding window
int result = sum;
for (int i = k; i < n; i++)
{
// Compute sum of k elements ending
// with a[i].
sum = sum + a[i] - a[i-k];
// Update result if required
result = Math.max(result, sum);
// Include maximum sum till [i-k] also
// if it increases overall max.
result = Math.max(result, sum + maxSum[i-k]);
}
return result;
}
// Driver method
public static void main(String[] args)
{
int arr[] = {1, 2, 3, -10, -3};
int k = 4;
System.out.println(maxSumWithK(arr, arr.length, k));;
}
}
Python3
# Python3 program to find largest subarray # sum with at-least k elements in it. # Returns maximum sum of a subarray # with at-least k elements. def maxSumWithK(a, n, k): # maxSum[i] is going to store # maximum sum till index i such # that a[i] is part of the sum. maxSum = [0 for i in range(n)] maxSum[0] = a[0] # We use Kadane's algorithm to fill maxSum[] # Below code is taken from method3 of # https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ curr_max = a[0] for i in range(1, n): curr_max = max(a[i], curr_max + a[i]) maxSum[i] = curr_max # Sum of first k elements sum = 0 for i in range(k): sum += a[i] # Use the concept of sliding window result = sum for i in range(k, n): # Compute sum of k elements # ending with a[i]. sum = sum + a[i] - a[i-k] # Update result if required result = max(result, sum) # Include maximum sum till [i-k] also # if it increases overall max. result = max(result, sum + maxSum[i-k]) return result # Driver code a = [1, 2, 3, -10, -3] k = 4 n = len(a) print(maxSumWithK(a, n, k)) # This code is contributed by Anant Agarwal.
C#
// C# program to find largest subarray sum with
// at-least k elements in it.
using System;
class Test
{
// Returns maximum sum of a subarray with at-least
// k elements.
static int maxSumWithK(int[] a, int n, int k)
{
// maxSum[i] is going to store maximum sum
// till index i such that a[i] is part of the
// sum.
int[] maxSum = new int [n];
maxSum[0] = a[0];
// We use Kadane's algorithm to fill maxSum[]
// Below code is taken from method 3 of
// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
int curr_max = a[0];
for (int i = 1; i < n; i++)
{
curr_max = Math.Max(a[i], curr_max+a[i]);
maxSum[i] = curr_max;
}
// Sum of first k elements
int sum = 0;
for (int i = 0; i < k; i++)
sum += a[i];
// Use the concept of sliding window
int result = sum;
for (int i = k; i < n; i++)
{
// Compute sum of k elements ending
// with a[i].
sum = sum + a[i] - a[i-k];
// Update result if required
result = Math.Max(result, sum);
// Include maximum sum till [i-k] also
// if it increases overall max.
result = Math.Max(result, sum + maxSum[i-k]);
}
return result;
}
// Driver method
public static void Main()
{
int[] arr = {1, 2, 3, -10, -3};
int k = 4;
Console.Write(maxSumWithK(arr, arr.Length, k));;
}
}
PHP
<?php
// PHP program to find largest subarray
// sum with at-least k elements in it.
// Returns maximum sum of a subarray
// with at-least k elements.
function maxSumWithK($a, $n, $k)
{
// maxSum[i] is going to
// store maximum sum till
// index i such that a[i]
// is part of the sum.
$maxSum[0] = $a[0];
// We use Kadane's algorithm
// to fill maxSum[]
$curr_max = $a[0];
for ($i = 1; $i < $n; $i++)
{
$curr_max = max($a[$i], $curr_max+$a[$i]);
$maxSum[$i] = $curr_max;
}
// Sum of first k elements
$sum = 0;
for ($i = 0; $i < $k; $i++)
$sum += $a[$i];
// Use the concept of
// sliding window
$result = $sum;
for ($i = $k; $i < $n; $i++)
{
// Compute sum of k
// elements ending
// with a[i].
$sum = $sum + $a[$i] - $a[$i - $k];
// Update result if required
$result = max($result, $sum);
// Include maximum sum till [i-k] also
// if it increases overall max.
$result = max($result, $sum +
$maxSum[$i - $k]);
}
return $result;
}
// Driver code
$a= array (1, 2, 3, -10, -3);
$k = 4;
$n = sizeof($a);
echo maxSumWithK($a, $n, $k);
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to find largest subarray sum with
// at-least k elements in it.
// Returns maximum sum of a subarray with at-least
// k elements.
function maxSumWithK(a, n, k)
{
// maxSum[i] is going to store maximum sum
// till index i such that a[i] is part of the
// sum.
let maxSum = new Array(n);
maxSum[0] = a[0];
// We use Kadane's algorithm to fill maxSum[]
// Below code is taken from method 3 of
// https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
let curr_max = a[0];
for (let i = 1; i < n; i++)
{
curr_max = Math.max(a[i], curr_max+a[i]);
maxSum[i] = curr_max;
}
// Sum of first k elements
let sum = 0;
for (let i = 0; i < k; i++)
sum += a[i];
// Use the concept of sliding window
let result = sum;
for (let i = k; i < n; i++)
{
// Compute sum of k elements ending
// with a[i].
sum = sum + a[i] - a[i-k];
// Update result if required
result = Math.max(result, sum);
// Include maximum sum till [i-k] also
// if it increases overall max.
result = Math.max(result, sum + maxSum[i-k]);
}
return result;
}
let arr = [1, 2, 3, -10, -3];
let k = 4;
document.write(maxSumWithK(arr, arr.length, k));
// This code is contributed by rameshtravel07.
</script>
Producción
-4
Aquí hay otro enfoque:
- Primero calcularemos la suma hasta k números y la almacenaremos en la suma.
- Luego tomaremos otra variable «última» e inicializaremos con cero. Esta variable «última» almacenará la suma de los números anteriores.
- Ahora haga un bucle para i = k a i<n y almacene la suma en la variable «sum» y tome j=0 y haga last += arr[j] si last se vuelve menor que cero como en el algoritmo de Kadane restamos last de sum y establecemos last = 0 y repite esto hasta llegar al final.
C++
#include <bits/stdc++.h>
using namespace std;
long long int maxSumWithK(long long int a[],
long long int n, long long int k)
{
long long int sum = 0;
for (long long int i = 0; i < k; i++) {
sum += a[i];
}
long long int last = 0;
long long int j = 0;
long long int ans = LLONG_MIN;
ans = max(ans, sum);
for (long long int i = k; i < n; i++) {
sum = sum + a[i];
last = last + a[j++];
ans = max(ans, sum);
if (last < 0) {
sum = sum - last;
ans = max(ans, sum);
last = 0;
}
}
return ans;
}
// Driver code
int main()
{
long long int a[] = { 1, 2, 3, -10, -3 };
long long int k = 4;
long long int n = sizeof(a) / sizeof(a[0]);
cout << maxSumWithK(a, n, k);
return 0;
}
Java
// Java program to implement the approach
class GFG {
// function to find the largest subarray sum
// with atleast k elements in it
// using Kadane's algorithm
static long maxSumWithK(long[] a, long n, int k)
{
// calculating sum of the first k elements
// of the array
long sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i];
}
long last = 0;
int j = 0;
long ans = Long.MIN_VALUE;
ans = Math.max(ans, sum);
// iterating over the subarrays
// and updating the sum accordingly
for (int i = k; i < n; i += 1) {
sum = sum + a[i];
last = last + a[j++];
// using sliding window
// to update the ans
ans = Math.max(ans, sum);
if (last < 0) {
sum = sum - last;
ans = Math.max(ans, sum);
last = 0;
}
}
return ans;
}
public static void main(String[] args) {
long[] arr = { 1, 2, 3, -10, -3 };
int k = 4;
long n = arr.length;
// Function Call
System.out.println(maxSumWithK(arr, n, k));
}
}
// This code is contributed by phasing17
Python3
import sys def maxSumWithK(a, n, k): sum = 0 for i in range(k): sum += a[i] last = 0 j = 0 ans = -sys.maxsize - 1 ans = max(ans, sum) for i in range(k, n): sum = sum + a[i] last = last + a[j] j += 1 ans = max(ans, sum) if(last < 0): sum = sum-last ans = max(ans, sum) last = 0 return ans # Driver code a = [1, 2, 3, -10, -3] k = 4 n = len(a) print(maxSumWithK(a, n, k)) # This code is contributed by shinjanpatra
C#
// C# program to implement the approach
using System;
public class GFG {
// function to find the largest subarray sum
// with atleast k elements in it
// using Kadane's algorithm
static long maxSumWithK(long[] a, long n, long k)
{
// calculating sum of the first k elements
// of the array
long sum = 0;
for (long i = 0; i < k; i++) {
sum += a[i];
}
long last = 0;
long j = 0;
long ans = Int64.MinValue;
ans = Math.Max(ans, sum);
// iterating over the subarrays
// and updating the sum accordingly
for (long i = k; i < n; i++) {
sum = sum + a[i];
last = last + a[j++];
// using sliding window
// to update the ans
ans = Math.Max(ans, sum);
if (last < 0) {
sum = sum - last;
ans = Math.Max(ans, sum);
last = 0;
}
}
return ans;
}
// Driver Code
public static void Main(string[] args)
{
long[] arr = { 1, 2, 3, -10, -3 };
long k = 4;
long n = arr.Length;
// Function Call
Console.WriteLine(maxSumWithK(arr, n, k));
}
}
Javascript
<script>
function maxSumWithK(a, n, k){
let sum = 0
for(let i = 0; i < k; i++)
sum += a[i]
let last = 0
let j = 0
let ans = Number.MIN_VALUE
ans = Math.max(ans,sum)
for(let i = k; i < n; i++)
{
sum = sum + a[i]
last = last + a[j]
j += 1
ans = Math.max(ans,sum)
if(last < 0)
{
sum = sum-last
ans = Math.max(ans,sum)
last = 0
}
}
return ans
}
let arr = [1, 2, 3, -10, -3];
let k = 4;
document.write(maxSumWithK(arr, arr.length, k));
// This code is contributed by shinjanpatra
</script>
Producción
-4
Complejidad de tiempo: O(n)
Este artículo es una contribución de Rakesh Kumar . 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.
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