Hello! I’m having trouble using binary search (after calculating the partial sum) to complete the following problem, specifically the condition of displaying the smallest result. Any hints are appreciated. (I did the brute force approach successfully but I’m really interested in the binary search one)
a[n]be a set of strictly positive numbers. Two indices i and j
1 ≤ i < j < ndivide the set so that
X = a + a + ... + a[i],
Y = a[i+1] + a[i+2] + ... + a[j]and
Z = a[j+1] + a[j+2] + ... + a[n].
Find two indices i and j ,so that max(X,Y,Z) - min(X,Y,Z) is minimum. . If there is more than one solution display the one for which
iis the smallest, and if there’s more than one solution with the same ‘i’, display the one where ‘j’ is the smallest.
Example: for input 1 3 4 2 1 2 10 5 8 6 -> the output should be
i = 5and
j = 7. In this case
X = 13,
Y = 15,
Z = 14. The difference
max(X, Y, Z) - min(X, Y, Z) = 15-13 = 2