使用分而治之的最小前缀数组

Question

我正在努力解决一个分而治之的问题，因为我无法完全理解它。假设我们有一些数组 X[1:n]。我们如何找到最小前缀数组 X[1:k]，其中 1 ≤ k ≤ n 并且前缀定义为实数数组的 X[1]×X[2]×...×X[n]？

到目前为止我的方法是：

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

我认为这不是一个有效的分而治之的解决方案，因为我仍然需要遍历数组中的每个元素。

编辑：

我能想到的最好的例子：

考虑数组 {-1,2,2,2}，最小前缀为 k=3，因为当所有元素相乘时，结果答案为 -6。

但是，如果我们再考虑数组 {-1,2,-2,2}，那么最小前缀将是 k=1，因为 k[0]*k[1] = -2 从第 3 个元素开始相乘只会使数字变大。

Answer 1

寻找“最小前缀积”的算法基本上是计算所有可能的前缀并找到其中的最小值。这可以在线性时间内完成，而且不会更快。

伪代码：

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

问题中最奇怪的部分是“分而治之”的要求。我想，如果你眯着眼睛看这个算法，你可能会说，它是“分而治之”，至于计算长度的前缀 i 它使用先前计算的长度前缀 i-1.

为了说明这一点，可以将算法重写为递归函数：

# 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)

注：

在递归变体中，space 复杂度从 O(1) 变为 O(n)，函数可以重写为尾递归以避免
为简化代码，有意未考虑空数组和乘积溢出等极端情况

使用分而治之的最小前缀数组

Min-prefix-array using divide and conquer

arrays

algorithm

divide-and-conquer