algorithm - 以最小差异对数组进行分区

Question

给定一个 A 的 N 整数数组。我需要找到 X 使得以下 2 个值 (A[1] * A[2] * ... * A[X]) 和 (A[X+1] * A[X+2] * ... * A[N]) 是最小可能的，即我需要最小化 | (A[1] * A[2] * ... * A[X]) - (A[X+1] * A[X+2] * ... * A[N]) |如果 X 有多个这样的值，则打印最小的一个。

约束:-

• 1 <= N <= 10^5

• 1 <= A[i] <= 10^18.

我无法找到有效解决此问题的方法。解决这个问题的最佳方法应该是什么。有没有什么特殊的算法可以实现大数相乘。

Answer 1

想法是使用前缀和后缀产品的形式。

让:

1. pre[i] = A[1] * A[2] * ... A[i] 和
2. suf[i] = A[i] * A[i + 1] * ... A[N]

您可以在 O(n) 时间内计算这些数组，如:

• pre[i] = A[i] * pre[i - 1] 与 pre[1] = A[i] 和

• suf[i] = A[i] * suf[i + 1] 和 suf[N] = A[n]

然后，从 i = 1 迭代到 N 并计算以下项的最大值:

abs(pre[i] - suf[i + 1])

观察 pre[i] - suf[i + 1] 与:

(A[1] * A[2] * ... * A[i]) - (A[i + 1] * A[i + 2] ... * A[N])

这正是您想要计算的。