I need to create an algorithm that takes an array A as an argument and finds a subarray of A whose sum of elements multiplied by the smallest element in that subarray yields the greatest value. Values in A are positive and we cannot change the order in that array.
I was told that its possible to do in O(nlogn). I was thinking about some sort of Divide and Conquer algorithm to obey brute force approach.
Any Ideas?
We can have divide and conquer in O(n log n) by evaluating:
f(whole_section) =
max(
f'(whole_section),
f(left_half),
f(right_half)
)
Where f' evaluates the maximum value for a section that includes at least one element fron the left side and one from the right (or at least the single middle element in case of an odd-numbered whole section).
To understand how f' can be calculated in O(n) consider the following example. Say g below is the smaller of g and h.
abcdefghijklmn
^^
Expand the interval in both directions until the next element smaller than g is encountered.
abcdefghijklmn
^ ^
Say j is now the next smallest (e is smaller than j so we end the current interval at f on the left).
Our sum and multiplier can be updated in O(1) each time we move a pointer. Calculate for g * sum and expand the interval again, this time with j as the smallest. Note that multiple j values can be passed by the pointers in either direction.
abcdefghijklmn
^ ^
This time l is the next smaller after j and e is even smaller. Calculate for j * sum and keep going.
Since each element during the interval expansion is visited at most once, f' can be evaluated in O(n) and since we halve the number of elements with each recursive call to f, f can be evaluated in O(n log n).