C++程序查找第 k 大的子数组之和

给定一个整数数组。编写一个程序，在其中寻找具有负数和正数的数字的连续子数组的第k大的和。

例子:

Input: a[] = {20, -5, -1} 
         k = 3
Output: 14
Explanation: 所有连续子数组的和为(20, 15, 14, -5, -6, -1)，因此第3大的和为14。

Input: a[] = {10, -10, 20, -40} 
         k = 6
Output: -10 
Explanation: 所有连续子数组的和的第6大值是-10。

一种 暴力破解的方法 是将所有连续和存储在另一个数组中，然后对其进行排序并打印第k大的值。但是，当元素的数量很大时，在存储连续和的数组中，由于连续子数组的数量将会很大（二次方），所以该方法将会消耗大量的内存。

一种 高效的方法 是在sum[]数组中存储该数组的预和。我们可以根据索引i和j来寻找从i到j的连续子数组的和，公式如下：sum[j] – sum[i-1]。

为了存储第k大的和，可以使用小根堆（优先队列），其中我们将连续和压入小根堆中，直到我们得到K个元素，一旦我们有了K个元素，就检查该元素是否大于插入到小根堆中的第K个元素，如果是，则将其插入到小根堆中并弹出小根堆中的顶部元素，否则不插入。最后，小根堆中的顶部元素将是您的答案。

下面是上述方法的实现。

// 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 predix 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;
}

输出: