c++ - 有没有办法使用分而治之来计算数组改变符号的次数

Question

假设有一个数组 A = {1, -1, 1, 1, 1, -1, 1} 有没有办法使用分治法计算数组元素改变符号的次数？例如：从 -1 到 1 和 1 到 -1。

我试图实现一个解决方案，将数组划分为 2 个子数组并计算左子数组的最后一个元素乘以右子数组的右元素是否小于 0，在这种情况下符号改变了。

这是我试图实现的伪代码：

Find Number of Roots(vector V)
  n = V.size()  
  if n <= 1
    return 0
  end if
else
  number_of_roots = 0
  lower_half = Roots(V[1...n/2])
  upper_half = Roots(V[n/2+1...n])

  if (lower_half.back() * upper_half.front() < 0)
  number_of_roots++

  return number_of_roots
 end else
end program

标签： c++algorithm