给定一个整数数组和一个整数值k, 找出k个子数组(可能重叠), 它们具备k个最大和。

例子：

Input : arr = {4, -8, 9, -4, 1, -8, -1, 6}, k = 4Output : 9 6 6 5Input : arr = {-2, -3, 4, -1, -2, 1, 5, -3}, k= 3Output : 7 6 5

应用Kadane的算法咱们能够找到一个数组的最大间断子数组总和。然而在这种状况下Kadane的算法不起作用。正如咱们在数组中命中正数时一样, 将max_ending_here变量设置为零, 因而咱们错过了第二个最大值的可能性。

这是咱们提出的一种算法宋恩培和高冈忠雄计算最大子阵列和问题在O(n)工夫中, k个最大子数组和问题在O(k * n)工夫中。

首先, 咱们应用这种办法钻研仅最大子数组和的问题：

先决条件：

  1. 前缀和数组
  2. 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 less than all values of mini, then               include it in mini and remove the maximum element from 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 ++

// 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 arrayvector< 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 candvoid 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 neededvoid 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 sumsvoid 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 Programint 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

# Python program to find out k maximum sum of# overlapping sub-arrays  # Function to compute prefix-sum of the input arraydef 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 canddef 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 neededdef 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 sumsdef 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 1arr1 = [ 4 , - 8 , 9 , - 4 , 1 , - 8 , - 1 , 6 ]k1 = 4kMaxOvSubArray(arr1, k1)  # Test case 2arr2 = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ]k2 = 3kMaxOvSubArray(arr2, k2)

输入如下：

9 6 6 57 6 5

工夫复杂度：" insertMini"和" maxMerge"函数的运行工夫为O(k), 而更新" cand"数组则须要O(k)工夫。咱们执行此过程n次。因而, 整体工夫复杂度为O(k * n).

更多数据结构和算法相干内容请参考：lsbin - IT开发技术：https://www.lsbin.com/

查看以下更多算法相干的内容：

  • FCFS CPU调度算法程序实现：https://www.lsbin.com/3839.html
  • 如何从列题目中查找Excel列号？：https://www.lsbin.com/3737.html
  • 如何计算两个数组中的最大求和门路？：https://www.lsbin.com/3689.html