Min-prefix-array using divide and conquer-CodePudding

I am struggling to work on a divide-and-conquer problem as I can't quite wrap my head around it. Lets say we have some array X[1:n]. How would we go about finding the min-prefixarray X[1:k] where 1 ≤ k ≤ n and the prefix is defined as X[1]×X[2]×...×X[n] for an array of real numbers?

My approach so far has been:

function min_prefix(array[1:n],n)
begin
    if array.length == 1 then
        return n, array[0], array[0]
    endif
    
    
integer best_k, real b_total, total = min_prefix([1:n-1],n-1)

new_total = total*array[n]

if  new_total < b_total then
    return n, new_total, new_total
endif

return best_k, b_total, new_total
    end

I dont think this is a valid divide-and-conquer solution as I still have to iterate over every element in the array.

Edit:

The best example I could think of:

Consider the array {-1,2,2,2} the min-prefix would be k=3 as, when all the elements are multiplied together the resultant answer is -6.

However if we then consider the array {-1,2,-2,2} then the min prefix would be k=1 as k[0]*k[1] = -2 multiplying the 3rd element onwards would only make the number larger.

CodePudding user response：

The algorithm to find the "minimal prefix product" is, basically, to calculate all possible prefixes and find the minimum among them. This can be done in linear time, and not faster.

Pseudocode:

min_pref_l = 1
min_pref_v = arr[0]
prev_f = arr[0]

for i in 1 until arr.length:
  pref_v *= arr[i]
  if pref_v < min_pref_v:
    min_pref_v = pref_v
    min_pref_l = i   1

return min_pref_v, min_pref_l

The strangest part of the question is the "divide and conquer" requirement. I think, if you squint hard enough and look at this algorithm, you can probably say, that it's "divide and conquer", as for calculating the prefix of length i it uses the previously calculated prefix of length i-1.

To illustrate that, the algorithm could be rewritten as a recursive function:

# min_prefix returns tuple of three values:
# First two define the minimal prefix of length ≤ i, as the pair of (value, length)
# Third is the product of the prefix of length i
fun min_prefix(i: int) -> (int, int, int):
   if i == 0:
     return arr[0], 1, arr[0]
   
   prev_min_l, prev_min_v, prev_v = min_prefix(i-1)
   v = prev_v * arr[i]
   if v < prev_min_v:
     return i 1, v, v
   else:
     return prev_min_l, prev_min_v, v

# program result
return min_prefix(arr.length - 1)

Note:

in the recursive variant the space complexity went from O(1) to O(n), the function can be rewritten as tail recursive to avoid that
corner cases, such as empty array and product overflow were not considered intentionally, to simplify the code