Compruebe si el producto de las K sumas más grandes de subarreglos es mayor que M

Dada una array arr[] de N enteros y dos enteros M y K . La tarea es verificar si el producto de la K suma más grande de subarreglos contiguos es mayor que M . Ejemplos:

Entrada: arr[] = {10, -4, -2, 7}, M = 659, K = 3 Salida: Sí Las 3 sumas contiguas más grandes para los subarreglos son de los subarreglos {10, -4, -2, 7 }, {10} y {7}, es decir, 11, 10 y 7, el producto es 11 * 10 * 7 = 770, que es mayor que 659. Entrada: arr [] = {4, -3, 8}, M = 100 , K = 6 Salida: No

Un enfoque de fuerza bruta es almacenar toda la suma del subarreglo contiguo en algún otro arreglo y ordenarlo, luego calcular el producto de la suma más grande de K y verificar si el valor es mayor que M. Pero en caso de que el tamaño del arreglo sea demasiado grande, el número de subarreglos continuos aumentará y, por lo tanto, el arreglo auxiliar ocupará más espacio. Un mejor enfoque es almacenar la suma del prefijo de la array en la propia array. Entonces la suma del subarreglo arr[i…j] se puede calcular como arr[j] – arr[i – 1] . Ahora para almacenar la Ksubarreglos contiguos de suma más grande, use un montón mínimo (cola de prioridad) en el que solo se almacenarán las K sumas máximas a la vez. Después de eso, para todos los demás elementos, verifique si el elemento es mayor que el elemento superior del montón mínimo, en caso afirmativo, ese elemento se insertará en el montón mínimo y el elemento superior se extraerá del montón mínimo. Al final, calcule el producto de todos los elementos en el montón mínimo y verifique si es mayor que M o no. A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true is the product
// of the maximum K subarrays sums of
// arr[] is greater than M
bool checkKSum(int arr[], int n, int k, int M)
{
    // Update the array to store the prefix sum
    for (int i = 1; i < n; i++)
        arr[i] = arr[i - 1] + arr[i];
 
    // Min-heap
    priority_queue<int, vector<int>, greater<int> > Q;
 
    // Starting index of the subarray
    for (int i = 0; i < n; i++) {
 
        // Ending index of the subarray
        for (int j = i; j < n; j++) {
 
            // To store the sum of the
            // subarray arr[i...j]
            int sum = (i == 0) ? arr[j] : arr[j] - arr[i - 1];
 
            // If the queue has less than k elements
            // then simply push it
            if (Q.size() < k)
                Q.push(sum);
 
            else {
 
                // If the min heap has equal exactly k
                // elements then check if the current
                // sum is greater than the smallest
                // of the current k sums stored
                if (Q.top() < sum) {
                    Q.pop();
                    Q.push(sum);
                }
            }
        }
    }
 
    // Calculate the product of
    // the k largest sum
    long product = 1;
    while (!Q.empty()) {
        product *= Q.top();
        Q.pop();
    }
 
    // If the product is greater than M
    if (product > M)
        return true;
 
    return false;
}
 
// Driver code
int main()
{
    int a[] = { 10, -4, -2, 7 };
    int n = sizeof(a) / sizeof(a[0]);
    int k = 3, M = 659;
 
    if (checkKSum(a, n, k, M))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// JAVA implementation of the approach
import java.util.*;
class GFG {
 
    // Function that returns true is the product
    // of the maximum K subarrays sums of
    // arr[] is greater than M
    public static boolean checkKSum(int arr[], int n, int k,
                                    int M)
    {
        // Update the array to store the prefix sum
        for (int i = 1; i < n; i++)
            arr[i] = arr[i - 1] + arr[i];
 
        // Min-heap
        PriorityQueue<Integer> Q
            = new PriorityQueue<Integer>();
 
        // Starting index of the subarray
        for (int i = 0; i < n; i++) {
 
            // Ending index of the subarray
            for (int j = i; j < n; j++) {
 
                // To store the sum of the
                // subarray arr[i...j]
                int sum = (i == 0) ? arr[j]
                                   : arr[j] - arr[i - 1];
 
                // If the queue has less than k elements
                // then simply push it
                if (Q.size() < k)
                    Q.add(sum);
 
                else {
 
                    // If the min heap has equal exactly k
                    // elements then check if the current
                    // sum is greater than the smallest
                    // of the current k sums stored
                    if (Q.poll() < sum) {
                        // Q.pop();
                        Q.add(sum);
                    }
                }
            }
        }
 
        // Calculate the product of
        // the k largest sum
        long product = 1;
        while (Q.isEmpty() == false) {
            product = product * Q.poll();
        }
 
        // If the product is greater than M
        if (product > M)
            return true;
 
        return false;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 10, -4, -2, 7 };
        int n = a.length;
        int k = 3, M = 659;
 
        if (checkKSum(a, n, k, M))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by Taranpreet

# Python3 implementation of the approach
# importing heapq python module to implement min heap
import heapq
 
# Function that returns true is the product
# of the maximum K subarrays sums of
# arr[] is greater than M
def checkKSum(arr, n, k, M):
   
    # Update the array to store the prefix sum
    for i in range(1, n):
        arr[i] += arr[i-1]
    Q = arr
     
    # creating Min-heap with heapify() inbuilt function
    heapq.heapify(Q)
     
    # Starting index of the subarray
    for i in range(n):
       
        # Ending index of the subarray
        for j in range(i, n):
           
            # To store the sum of the
            # subarray arr[i...j]
            if i == 0:
                sum = 0
            else:
                sum = arr[j] - arr[i - 1]
                 
            # If the queue has less than k elements
            # then simply push it
            if len(Q) < k:
                Q.append(sum)
                heapq.heapify(Q)
            else:
                # If the min heap has equal exactly k
                # elements then check if the current
                # sum is greater than the smallest
                # of the current k sums stored
                if Q[0] < sum:
                    Q[0] = sum
                    heapq.heapify(Q)
                     
    # Calculate the product of
    # the k largest sum
    product = 1
    for i in Q:
        product *= i
         
    # If the product is greater than M
    if product > M:
        return True
    return False
 
# Driver code
if __name__ == '__main__':
    a = [10, -4, -2, 7]
    n = len(a)
    k, M = 3, 659
    if checkKSum(a, n, k, M):
        print('Yes')
    else:
        print('No')
         
'''This Code is contributed by Rajat Kumar (GLAU)'''

// C# implementation of the approach
using System;
using System.Collections;
 
public class GFG
{
 
  // Function that returns true is the product
  // of the maximum K subarrays sums of
  // arr[] is greater than M
  public static bool checkKSum(int[] arr, int n, int k,
                               int M)
  {
 
    // Update the array to store the prefix sum
    for (int i = 1; i < n; i++)
      arr[i] = arr[i - 1] + arr[i];
 
    // Min-heap
    SortedList Q = new SortedList();
 
    // Starting index of the subarray
    for (int i = 0; i < n; i++) {
 
      // Ending index of the subarray
      for (int j = i; j < n; j++) {
 
        // To store the sum of the
        // subarray arr[i...j]
        int sum = (i == 0) ? arr[j]
          : arr[j] - arr[i - 1];
 
        // If the queue has less than k elements
        // then simply push it
        if (Q.Count < k)
          Q.Add(sum, sum);
 
        else {
 
          // If the min heap has equal exactly k
          // elements then check if the current
          // sum is greater than the smallest
          // of the current k sums stored
          int elem = (int)Q.GetByIndex(0);
          Q.RemoveAt(0);
          if (elem < sum) {
            // Q.pop();
            Q.Add(sum, sum);
          }
        }
      }
    }
 
    // Calculate the product of
    // the k largest sum
    long product = 1;
    while (Q.Count != 0) {
      int elem = (int)Q.GetByIndex(0);
      Q.RemoveAt(0);
      product = product * elem;
    }
 
    // If the product is greater than M
    if (product > M)
      return true;
 
    return false;
  }
  public static void Main(string[] args)
  {
    int[] a = { 10, -4, -2, 7 };
    int n = a.Length;
    int k = 3, M = 659;
 
    if (checkKSum(a, n, k, M))
      Console.WriteLine("Yes");
    else
      Console.WriteLine("No");
  }
}
 
// This code is contributed by phasing17

// JavaScript implementation of the approach
 
  // Function that returns true is the product
  // of the maximum K subarrays sums of
  // arr[] is greater than M
  function checkKSum(arr, n, k, M)
  {
      var elem;
      var sum;
 
    // Update the array to store the prefix sum
    for (var i = 1; i < n; i++)
      arr[i] += arr[i - 1];
 
    // Min-heap
    let Q = arr;
 
    // Starting index of the subarray
    for (var i = 0; i < n; i++) {
 
      // Ending index of the subarray
      for (var j = i; j < n; j++) {
 
        // To store the sum of the
        // subarray arr[i...j]
        if (i == 0)
            sum = 0;
        else
            sum = arr[j] - arr[i - 1];
        Q.sort();
 
        // If the queue has less than k elements
        // then simply push it
        if (Q.length < k)
        {
           Q.push(sum);
        }
        else {
 
          // If the min heap has equal exactly k
          // elements then check if the current
          // sum is greater than the smallest
          // of the current k sums stored
           
 
          if (Q[0] < sum) {
            Q[0] = sum;
             
          }
           
          Q.sort();
        }
      }
    }
     
     
    // Calculate the product of
    // the k largest sum
    var product = 1;
    for (var elem of Q)
      product *= elem;
     
 
    // If the product is greater than M
    if (product > M)
      return true;
 
    return false;
  }
 
let a = [ 10, -4, -2, 7 ];
let n = a.length;
let k = 3;
let M = 659;
 
    if (checkKSum(a, n, k, M))
      console.log("Yes");
    else
      console.log("No");
 
 
// This code is contributed by phasing17

Yes