使用分治法在 O(n) 时间内找到最大乘积

Question

我正在尝试使用在 O(n) 时间内运行的分治法来创建算法，它需要找到一组不同数字（可以是正数或负数）中两个数字之间的最大乘积。我一直在尝试使用 findMax 和 findMin 来解决这个问题，但我无法弄清楚。

Answer 1

你有一个数组A，这个数组可以分为两个子数组B和C。A的最大乘积是以下之一：

1. B 的最大乘积
2. C 的最大乘积
3. B 的最大正值乘以 C 的最大正值
4. B 的最大负值乘以 C 的最大负值

你必须能够在恒定时间内组合两个子数组：
给定 max_prod_B、largest_pos_B、largest_neg_B、max_prod_C、largest_pos_C、largest_neg_C，您可以创建（在恒定时间内）：

max_prod_A = max(max_prod_B,max_prod_C,最大_pos_B x 最大_pos_C,最大_neg_B x 最大_neg_C)
最大_位置_A = 最大（最大_位置_B，最大_位置_C）
最大的负值A = 最小(最大的负值B,最大的负值C)

aa...完成。