Programa Python3 para encontrar el subarreglo contiguo de suma más grande K-th

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.  

# 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 predix 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 

Producción:

-10

Complejidad de tiempo: O (n ^ 2 log (k)) 
Espacio auxiliar: O (k) para min-heap y podemos almacenar la array de suma en la array en sí, ya que no sirve.
¡ Consulte el artículo completo sobre K-ésimo subarreglo contiguo de suma más grande para obtener más detalles!