Dada una array de enteros. Escriba un programa para encontrar la K-ésima suma más grande de subarreglo contiguo dentro del arreglo de números que tiene números negativos y positivos.
Ejemplos:
Input: a[] = {20, -5, -1}
k = 3
Output: 14
Explanation: All sum of contiguous
subarrays are (20, 15, 14, -5, -6, -1)
so the 3rd largest sum is 14.
Input: a[] = {10, -10, 20, -40}
k = 6
Output: -10
Explanation: The 6th largest sum among
sum of all contiguous subarrays is -10.
Un enfoque de fuerza bruta es almacenar todas las sumas contiguas en otra array y clasificarla e imprimir la k-ésima más grande. Pero en el caso de que la cantidad de elementos sea grande, la array en la que almacenamos las sumas contiguas se quedará sin memoria ya que la cantidad de subarreglos contiguos será grande (orden cuadrático)
Un enfoque eficiente es almacenar la suma previa de la array en una array sum[]. Podemos encontrar la suma de subarreglo contiguo del índice i al j como sum[j]-sum[i-1]
Ahora, para almacenar la K-ésima suma más grande, use un montón mínimo (cola de prioridad) en el que empujamos las sumas contiguas hasta que obtengamos K elementos, una vez que tengamos nuestros K elementos, verifique si el elemento es mayor que el K-ésimo elemento en el que se inserta. el montón mínimo con la extracción del elemento superior en el montón mínimo, de lo contrario no se inserta. Al final, el elemento superior en el montón mínimo será su respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to find the k-th largest sum
// of subarray
#include <bits/stdc++.h>
using namespace std;
// function to calculate kth largest element
// in contiguous subarray sum
int kthLargestSum(int arr[], int n, int k)
{
// array to store prefix sums
int sum[n + 1];
sum[0] = 0;
sum[1] = arr[0];
for (int i = 2; i <= n; i++)
sum[i] = sum[i - 1] + arr[i - 1];
// priority_queue of min heap
priority_queue<int, vector<int>, greater<int> > Q;
// loop to calculate the contiguous subarray
// sum position-wise
for (int i = 1; i <= n; i++)
{
// loop to traverse all positions that
// form contiguous subarray
for (int j = i; j <= n; j++)
{
// calculates the contiguous subarray
// sum from j to i index
int x = sum[j] - sum[i - 1];
// if queue has less then k elements,
// then simply push it
if (Q.size() < k)
Q.push(x);
else
{
// it the min heap has equal to
// k elements then just check
// if the largest kth element is
// smaller than x then insert
// else its of no use
if (Q.top() < x)
{
Q.pop();
Q.push(x);
}
}
}
}
// the top element will be then kth
// largest element
return Q.top();
}
// Driver program to test above function
int main()
{
int a[] = { 10, -10, 20, -40 };
int n = sizeof(a) / sizeof(a[0]);
int k = 6;
// calls the function to find out the
// k-th largest sum
cout << kthLargestSum(a, n, k);
return 0;
}
Java
// Java program to find the k-th
// largest sum of subarray
import java.util.*;
class KthLargestSumSubArray
{
// function to calculate kth largest
// element in contiguous subarray sum
static int kthLargestSum(int arr[], int n, int k)
{
// array to store prefix sums
int sum[] = new int[n + 1];
sum[0] = 0;
sum[1] = arr[0];
for (int i = 2; i <= n; i++)
sum[i] = sum[i - 1] + arr[i - 1];
// priority_queue of min heap
PriorityQueue<Integer> Q = new PriorityQueue<Integer> ();
// loop to calculate the contiguous subarray
// sum position-wise
for (int i = 1; i <= n; i++)
{
// loop to traverse all positions that
// form contiguous subarray
for (int j = i; j <= n; j++)
{
// calculates the contiguous subarray
// sum from j to i index
int x = sum[j] - sum[i - 1];
// if queue has less then k elements,
// then simply push it
if (Q.size() < k)
Q.add(x);
else
{
// it the min heap has equal to
// k elements then just check
// if the largest kth element is
// smaller than x then insert
// else its of no use
if (Q.peek() < x)
{
Q.poll();
Q.add(x);
}
}
}
}
// the top element will be then kth
// largest element
return Q.poll();
}
// Driver Code
public static void main(String[] args)
{
int a[] = new int[]{ 10, -10, 20, -40 };
int n = a.length;
int k = 6;
// calls the function to find out the
// k-th largest sum
System.out.println(kthLargestSum(a, n, k));
}
}
/* This code is contributed by Danish Kaleem */
Python3
# Python program to find the k-th largest sum # of subarray import heapq # function to calculate kth largest element # in contiguous subarray sum def kthLargestSum(arr, n, k): # array to store prefix sums sum = [] sum.append(0) sum.append(arr[0]) for i in range(2, n + 1): sum.append(sum[i - 1] + arr[i - 1]) # priority_queue of min heap Q = [] heapq.heapify(Q) # loop to calculate the contiguous subarray # sum position-wise for i in range(1, n + 1): # loop to traverse all positions that # form contiguous subarray for j in range(i, n + 1): x = sum[j] - sum[i - 1] # if queue has less then k elements, # then simply push it if len(Q) < k: heapq.heappush(Q, x) else: # it the min heap has equal to # k elements then just check # if the largest kth element is # smaller than x then insert # else its of no use if Q[0] < x: heapq.heappop(Q) heapq.heappush(Q, x) # the top element will be then kth # largest element return Q[0] # Driver program to test above function a = [10,-10,20,-40] n = len(a) k = 6 # calls the function to find out the # k-th largest sum print(kthLargestSum(a,n,k)) # This code is contributed by Kumar Suman
C#
// C# program to find the k-th
// largest sum of subarray
using System;
using System.Collections.Generic;
public class KthLargestSumSubArray
{
// function to calculate kth largest
// element in contiguous subarray sum
static int kthLargestSum(int []arr, int n, int k)
{
// array to store prefix sums
int []sum = new int[n + 1];
sum[0] = 0;
sum[1] = arr[0];
for (int i = 2; i <= n; i++)
sum[i] = sum[i - 1] + arr[i - 1];
// priority_queue of min heap
List<int> Q = new List<int> ();
// loop to calculate the contiguous subarray
// sum position-wise
for (int i = 1; i <= n; i++)
{
// loop to traverse all positions that
// form contiguous subarray
for (int j = i; j <= n; j++)
{
// calculates the contiguous subarray
// sum from j to i index
int x = sum[j] - sum[i - 1];
// if queue has less then k elements,
// then simply push it
if (Q.Count < k)
Q.Add(x);
else
{
// it the min heap has equal to
// k elements then just check
// if the largest kth element is
// smaller than x then insert
// else its of no use
Q.Sort();
if (Q[0] < x)
{
Q.RemoveAt(0);
Q.Add(x);
}
}
Q.Sort();
}
}
// the top element will be then kth
// largest element
return Q[0];
}
// Driver Code
public static void Main(String[] args)
{
int []a = new int[]{ 10, -10, 20, -40 };
int n = a.Length;
int k = 6;
// calls the function to find out the
// k-th largest sum
Console.WriteLine(kthLargestSum(a, n, k));
}
}
// This code contributed by Rajput-Ji
JavaScript
<script>
// Javascript program to find the k-th largest sum
// of subarray
// function to calculate kth largest element
// in contiguous subarray sum
function kthLargestSum(arr, n, k)
{
// array to store prefix sums
var sum = new Array(n + 1);
sum[0] = 0;
sum[1] = arr[0];
for (var i = 2; i <= n; i++)
sum[i] = sum[i - 1] + arr[i - 1];
// priority_queue of min heap
var Q = [];
// loop to calculate the contiguous subarray
// sum position-wise
for (var i = 1; i <= n; i++)
{
// loop to traverse all positions that
// form contiguous subarray
for (var j = i; j <= n; j++)
{
// calculates the contiguous subarray
// sum from j to i index
var x = sum[j] - sum[i - 1];
// if queue has less then k elements,
// then simply push it
if (Q.length < k)
Q.push(x);
else
{
// it the min heap has equal to
// k elements then just check
// if the largest kth element is
// smaller than x then insert
// else its of no use
Q.sort();
if (Q[0] < x)
{
Q.pop();
Q.push(x);
}
}
Q.sort();
}
}
// the top element will be then kth
// largest element
return Q[0];
}
// Driver program to test above function
var a = [ 10, -10, 20, -40 ];
var n = a.length;
var k = 6;
// calls the function to find out the
// k-th largest sum
document.write(kthLargestSum(a, n, k));
</script>
-10
Complejidad de tiempo: O(n² log (k))
Espacio auxiliar: O(k) f o min-heap y podemos almacenar la array de suma en la propia array, ya que no sirve.
Este artículo es una contribución de Raja Vikramaditya . 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 contribuir@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