K maximum sums of overlapping contiguous sub-arrays

Software Development
#1

Hello Everyone,

Given an array of Integers and an Integer value k, find out k sub-arrays(may be overlapping), which have k maximum sums.

Method for k-maximum sub-arrays:

  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

Throughout this calculation method, we keep maxi in non-increasing and mini in non-decreasing order.

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

}

Output:

9 6 6 5 7 6 5

Time Complexity: The ‘insertMini’ and ‘maxMerge’ functions runs in O(k) time and it takes O(k) time to update the ‘cand’ array. We do this process for n times. Hence, the overall time complexity is O(k*n) .