human
Can you provide a code to k maximum sums of overlapping contiguous sub and the other steps required given the following:
K maximum sums of overlapping contiguous sub | 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 ..
Test case 1.
Test case 2"
How can the above be solved in Python?
assistant
#Here is code to k maximum sums of overlapping contiguous sub and the other steps required.
 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
def maxMerge ( maxi , 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
def insertMini ( mini , pre_sum ) :
	k = len ( mini )
	for i in range ( k ) :
		if ( pre_sum < mini [ i ] ) :
			mini . insert ( i , pre_sum )
			del mini [ - 1 ]
			break
def kMaxOvSubArray ( arr , k ) :
	n = len ( arr )
	pre_sum = prefix_sum ( arr , n )
	mini = [ float ( ' inf ' ) for i in range ( k ) ]
	mini [ 0 ] = 0
	maxi = [ - float ( ' inf ' ) for i in range ( k ) ]
	cand = [ 0 for i in range ( k ) ]
	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 ] )
	for ele in maxi :
		print ( ele , end = ' ▁ ' )
	print ( ' ' )
arr1 = [ 4 , - 8 , 9 , - 4 , 1 , - 8 , - 1 , 6 ]
k1 = 4
kMaxOvSubArray ( arr1 , k1 )
arr2 = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ]
k2 = 3
kMaxOvSubArray ( arr2 , k2 )