关于算法:算法题重叠的连续子数组的K个最大和

给定一个整数数组和一个整数值 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 的算法咱们能够找到一个数组的最大间断子数组总和。然而在这种状况下 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 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

# 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), 而更新 ” 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