# 第 K 個最大和的連續子數組 > 原文： [https://www.geeksforgeeks.org/k-th-largest-sum-contiguous-subarray/](https://www.geeksforgeeks.org/k-th-largest-sum-contiguous-subarray/) 給定一個整數數組。 編寫程序以在具有負數和正數的數字數組中找到連續的子數組的第`K`個最大和。 **示例**： ``` 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. ``` **暴力方法**方法是將所有連續的和存儲在另一個數組中并對其進行排序，然后打印出第`k`個最大的和。 但是在元素數量很大的情況下，我們存儲連續和的數組將耗盡內存，因為連續子數組的數量將很大（二次順序） 一種有效的**方法**將數組的前和存儲在`sum[]`數組中。 我們可以找到從索引`i`到`j`的連續子數組的和為`sum[j] - sum[i-1]` 現在要存儲第`K`個最大和，請使用最小堆（優先級隊列），在其中將連續和推入直到獲得`K`個元素，一旦有了`K`個元素，請檢查該元素是否大于第`K`個元素，插入最小堆并彈出最小堆中的頂部元素，否則不插入。 最后，最小堆中的最高元素將是您的答案。 下面是上述方法的實現。 ## C++ ```cpp // 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 contigous 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; } ```