Algorithm to find two subsets of an array which are maximum & equal

#1

Question is:

You have to place an electronic banner of a company as high as it can be, so that whole the city can view the banner standing on top of 2 pillars. The height of two pillars are to be chosen from given array… say [1, 2, 3, 4, 6]. We have to maximize the height of the two pillars standing side by side so that the pillars are of equal height and the banner can be placed on top of it. So for this case, maximum height is 8 and the pillar sets will be: [2,6], [4,3,1]

It is not necessary that all the elements of the array have to be used. Say, Array = [1,2,3,4,7] then maximum height is 7 and sets are [7], [4,3]

This problem is different from the subset sum problem in Dynamic programming because here all elements need not be part of the solution set.
I am trying to think of an approach to this problem and its extension, if instead of two pillars we have n pillars. Which is, how would the approach differ if we had to find n subsets of an array which are maximum & equal?

This question has a solution on stackoverflow which I am unable to fully grasp:



Please help in understanding the approach and the thought process.

#2

Hey!
the approach for solving this ques is to maintain a variable to keep the track of the of maximum(absolute difference, sum) and at last you will get the answer as (variable’s value) / 2.
for eg.
let the given array, arr = [1, 2, 3, 4, 6]
the variable to keep the track, max=0
then iterate in the array and take the maximum(absolute difference, sum)
1.
arr[0] = 1
diff = abs(arr[0] - max) => 1
sum = arr[0] + max => 1
max = maximum(sum, diff) => 1

arr[1] = 2
diff = abs(arr[1] - max) => 1
sum = arr[1] + max => 3
max = maximum(sum, diff) => 3

arr[2] = 3
diff = abs(arr[2] - max) => 0
sum = arr[2] + max => 6
max = maximum(sum, diff) => 6

arr[3] = 4
diff = abs(arr[3] - max) => 2
sum = arr[3] + max => 10
max = maximum(sum, diff) => 10

arr[4] = 6
diff = abs(arr[4] - max) => 4
sum = arr[4] + max => 16
max = maximum(sum, diff) => 16

after iterating in the whole array, value of max is 16.
so your answer is max / 2 = 8.