# 重疊的連續子數組的 K 個最大和 > 原文： [https://www.geeksforgeeks.org/k-maximum-sum-overlapping-contiguous-sub-arrays/](https://www.geeksforgeeks.org/k-maximum-sum-overlapping-contiguous-sub-arrays/) 給定一個整數數組和一個整數值`k`，找出`k`個最大和為`k`的子數組（可能重疊）。 **示例**： ``` Input : arr = {4, -8, 9, -4, 1, -8, -1, 6}, k = 4 Output : 9 6 6 5 Input : arr = {-2, -3, 4, -1, -2, 1, 5, -3}, k= 3 Output : 7 6 5 ``` 使用 [Kadane 的算法](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)，我們可以找到數組的最大連續子數組和。 但在[一些情況下](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)，Kadane 的算法不起作用。 當我們在數組中命中負數時，會將`max_ending_here`變量設置為零，因此我們錯過了第二個最大值的可能性。 這里我們是由 [Sung Eun Bae 和 Tadao Takaoka](http://ieeexplore.ieee.org/abstract/document/1300488/) 提出的算法，該算法計算`O(n)`時間中的[最大子數組和問題](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)和`O(k * n)`時間中的`k`個最大子數組和問題。 **首先，我們看一下使用這種方法的最大子數組和的問題**： **先決條件**： 1\. [前綴和數組](https://www.geeksforgeeks.org/prefix-sum-array-implementation-applications-competitive-programming/) 2\. [使用前綴和](https://www.geeksforgeeks.org/maximum-subarray-sum-using-prefix-sum/)的`O(n)`中最大子數組和。 **`k`個最大子數組的方法**： ``` 1\. Calculate the prefix sum of the input array. 2\. Take cand, maxi and mini as arrays of size k. 3\. Initialize mini[0] = 0 for the same reason as previous. 4\. for each value of the prefix_sum[i] do (i). update cand[j] value by prefix_sum[i] - mini[j] (ii). maxi will be the maximum k elements of maxi and cand (iii). if prefix_sum is minimum than all values of mini then include it in mini and remove maximum element form mini // After the ith iteration mini holds k minimum prefix sum upto // index i and maxi holds k maximum overlapping sub-array sums // upto index i. 5\. return maxi ``` 在整個計算方法中，我們將`maxi`保持不變，而`mini`則保持不變。 ## C++ ```cpp // C++ program to find out k maximum sum of // overlapping sub-arrays #include <iostream> #include <limits> #include <vector> using namespace std; // Function to compute prefix-sum of the input array vector<int> prefix_sum(vector<int> arr, int n) { ????vector<int> pre_sum; ????pre_sum.push_back(arr[0]); ????for (int i = 1; i < n; i++)? ????????pre_sum.push_back(pre_sum[i - 1] + arr[i]);???? ????return pre_sum; } // Update maxi by k maximum values from maxi and cand void maxMerge(vector<int>& maxi, vector<int> cand) { ????// Here cand and maxi arrays are in non-increasing ????// order beforehand. Now, j is the index of the ????// next cand element and i is the index of next ????// maxi element. Traverse through maxi array. ????// If cand[j] > maxi[i] insert cand[j] at the ith ????// position in the maxi array and remove the minimum ????// element of the maxi array i.e. the last element ????// and increase j by 1 i.e. take the next element ????// from cand. ????int k = maxi.size(); ????int j = 0; ????for (int i = 0; i < k; i++) { ????????if (cand[j] > maxi[i]) { ????????????maxi.insert(maxi.begin() + i, cand[j]); ????????????maxi.erase(maxi.begin() + k); ????????????j += 1; ????????} ????} } // Insert prefix_sum[i] to mini array if needed void insertMini(vector<int>& mini, int pre_sum) { ????// Traverse the mini array from left to right. ????// If prefix_sum[i] is less than any element ????// then insert prefix_sum[i] at that position ????// and delete maximum element of the mini array ????// i.e. the rightmost element from the array. ????int k = mini.size(); ????for (int i = 0; i < k; i++) { ????????if (pre_sum < mini[i]) { ????????????mini.insert(mini.begin() + i, pre_sum); ????????????mini.erase(mini.begin() + k); ????????????break; ????????} ????} } // Function to compute k maximum overlapping sub- // array sums void kMaxOvSubArray(vector<int> arr, int k) { ????int n = arr.size(); ????// Compute the prefix sum of the input array. ????vector<int> pre_sum = prefix_sum(arr, n); ????// Set all the elements of mini as +infinite ????// except 0th. Set the 0th element as 0\. ????vector<int> mini(k, numeric_limits<int>::max()); ????mini[0] = 0; ????// Set all the elements of maxi as -infinite. ????vector<int> maxi(k, numeric_limits<int>::min()); ????// Initialize cand array. ????vector<int> cand(k); ????// For each element of the prefix_sum array do: ????// compute the cand array. ????// take k maximum values from maxi and cand ????// using maxmerge function. ????// insert prefix_sum[i] to mini array if needed ????// using insertMini function. ????for (int i = 0; i < n; i++) { ????????for (int j = 0; j < k; j++) { ?????????????if(pre_sum[i] < 0 && mini[j]==numeric_limits<int>::max()) ???????????cand[j]=(-pre_sum[i])-mini[j]; ?????????else cand[j] = pre_sum[i] - mini[j]; ????????} ????????maxMerge(maxi, cand); ????????insertMini(mini, pre_sum[i]); ????} ????// Elements of maxi array is the k ????// maximum overlapping sub-array sums. ????// Print out the elements of maxi array. ????for (int ele : maxi) ????????cout << ele << " "; ????cout << endl; } // Driver Program int main() { ????// Test case 1 ????vector<int> arr1 = { 4, -8, 9, -4, 1, -8, -1, 6 }; ????int k1 = 4; ????kMaxOvSubArray(arr1, k1); ????// Test case 2 ????vector<int> arr2 = { -2, -3, 4, -1, -2, 1, 5, -3 }; ????int k2 = 3; ????kMaxOvSubArray(arr2, k2); ????return 0; } ``` ## Python3 ```py # Python program to find out k maximum sum of # overlapping sub-arrays # Function to compute prefix-sum of the input array def prefix_sum(arr, n): ????pre_sum = list() ????pre_sum.append(arr[0]) ????for i in range(1, n): ????????pre_sum.append(pre_sum[i-1] + arr[i]) ????return pre_sum # Update maxi by k maximum values from maxi and cand def maxMerge(maxi, cand): ????# Here cand and maxi arrays are in non-increasing ????# order beforehand. Now, j is the index of the ????# next cand element and i is the index of next ????# maxi element. Traverse through maxi array. ????# If cand[j] > maxi[i] insert cand[j] at the ith ????# position in the maxi array and remove the minimum ????# element of the maxi array i.e. the last element ????# and increase j by 1 i.e. take the next element ????# from cand. ????k = len(maxi) ????j = 0 ????for i in range(k): ????????if (cand[j] > maxi[i]): ????????????maxi.insert(i, cand[j]) ????????????del maxi[-1] ????????????j += 1 # Insert prefix_sum[i] to mini array if needed def insertMini(mini, pre_sum): ????# Traverse the mini array from left to right. ????# If prefix_sum[i] is less than any element ????# then insert prefix_sum[i] at that position ????# and delete maximum element of the mini array ????# i.e. the rightmost element from the array. ????k = len(mini) ????for i in range(k): ????????if (pre_sum < mini[i]): ????????????mini.insert(i, pre_sum) ????????????del mini[-1] ????????????break # Function to compute k maximum overlapping sub-array sums def kMaxOvSubArray(arr, k): ????n = len(arr) ????# Compute the prefix sum of the input array. ????pre_sum = prefix_sum(arr, n) ????# Set all the elements of mini as + infinite ????# except 0th. Set the 0th element as 0\. ????mini = [float('inf') for i in range(k)] ????mini[0] = 0 ????# Set all the elements of maxi as -infinite. ????maxi = [-float('inf') for i in range(k)] ????# Initialize cand array. ????cand = [0 for i in range(k)] ????# For each element of the prefix_sum array do: ????# compute the cand array. ????# take k maximum values from maxi and cand ????# using maxmerge function. ????# insert prefix_sum[i] to mini array if needed ????# using insertMini function. ????for i in range(n): ????????for j in range(k): ????????????cand[j] = pre_sum[i] - mini[j] ????????maxMerge(maxi, cand) ????????insertMini(mini, pre_sum[i]) ????# Elements of maxi array is the k ????# maximum overlapping sub-array sums. ????# Print out the elements of maxi array. ????for ele in maxi: ????????print(ele, end = ' ') ????print('') # Driver Program # Test case 1 arr1 = [4, -8, 9, -4, 1, -8, -1, 6] k1 = 4 kMaxOvSubArray(arr1, k1) # Test case 2 arr2 = [-2, -3, 4, -1, -2, 1, 5, -3] k2 = 3 kMaxOvSubArray(arr2, k2) ``` **輸出**： ``` 9 6 6 5 7 6 5 ``` **時間復雜度**：`insertMini`和`maxMerge`函數以`O(k)`時間運行，并且需要`O(k)`時間來更新`cand`數組。 我們執行此過程`n`次。 因此，總時間復雜度為`O(k * n)`。 * * * * * *