K maximum sums of overlapping contiguous sub | C ++ program to find out k maximum sum of overlapping sub - arrays ; Function to compute prefix - sum of the input array ; Update maxi by k maximum values from maxi and 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 . ; Insert prefix_sum [ i ] to mini array if needed ; 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 . ; Function to compute k maximum overlapping sub - array sums ; Compute the prefix sum of the input array . ; Set all the elements of mini as + infinite except 0 th . Set the 0 th element as 0. ; Set all the elements of maxi as - infinite . ; Initialize cand array . ; 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 . ; Elements of maxi array is the k maximum overlapping sub - array sums . Print out the elements of maxi array . ; Driver Program ; Test case 1 ; Test case 2
#include <iostream> NEW_LINE #include <limits> NEW_LINE #include <vector> NEW_LINE using namespace std ; 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 ; } void maxMerge ( vector < int > & maxi , vector < int > 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 ; } } } void insertMini ( vector < int > & mini , int pre_sum ) { 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 ; } } } void kMaxOvSubArray ( vector < int > arr , int k ) { int n = arr . size ( ) ; vector < int > pre_sum = prefix_sum ( arr , n ) ; vector < int > mini ( k , numeric_limits < int > :: max ( ) ) ; mini [ 0 ] = 0 ; vector < int > maxi ( k , numeric_limits < int > :: min ( ) ) ; vector < int > cand ( k ) ; 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 ] ) ; } for ( int ele : maxi ) cout << ele << " ▁ " ; cout << endl ; } int main ( ) { vector < int > arr1 = { 4 , -8 , 9 , -4 , 1 , -8 , -1 , 6 } ; int k1 = 4 ; kMaxOvSubArray ( arr1 , k1 ) ; vector < int > arr2 = { -2 , -3 , 4 , -1 , -2 , 1 , 5 , -3 } ; int k2 = 3 ; kMaxOvSubArray ( arr2 , k2 ) ; return 0 ; }