Stable merge of unsorted arrays to maximum sum?

#1

I saw a problem and wanted to know that the community thought about it:

Given two unsorted arrays, swap values from the second array into the first (stable) in order to find the maximum contiguous sum of the first array.

Eg. {3,1,4,5,6} and {9,1,2,5,3} ===> {9,5,4,5,6} and {3,1,2,5,1}

I can’t find a better solution than sorting and choosing the largest elements. Any thoughts?

0 Likes
#2

I am a little confused about the last sentence, sorting then choosing the largest elements, doesnt that violate the stability requirement?

I think what you are asking is how to replace A[i]s by B[j]s to maximize the subarray sum in A subject to the constraint that if A[i] is replaced by B[j] then A[i’>i] can only be replaced b B[j’] where j’ > j.

It’s a cute problem, and I think you can solve it with Dynamic Programming (knowing max subarray sum for A[0:i], B[0:j], find the max subarray for A[0:i+1] and B[0:j+1]), but will hold off till you confirm my interpretation,

cheers,
adnan

1 Like
#3

Thanks, Adnan. Yeah your interpretation is correct and more accurate than my original description :smile:

Looking forward to your solution.

0 Likes