algorithm - 使用分而治之算法在未排序的数组中查找最大和

Question

我将 n 个实数序列存储在一个数组中，A[1]、A[2]、…、A[n]。我正在尝试实现一个分而治之的算法来找到两个数字 A[i] 和 A[j]，其中 i < j，这样 A[i] ≤ A[j] 并且它们的和是最大的。

例如。 {2, 5, 9, 3, -2, 7} 将给出 14 的输出(5+9，而不是 16=9+7)。谁能给我一些关于如何做的想法？

提前致谢。

Answer 1

这个问题不太适合分而治之的方法。
很容易观察到如果 (i, j) 是这个问题的解，那么 A[j] >= A[k] 对于每个 k > j，即 A[j] 是 A[j..n] 中的最大值

证明:如果存在这样的k > j且A[k] > A[j]，则(j, k)是比(i, j)更好的解

因此我们只需要考虑满足该条件的j。

算法(伪代码)

maxj = n
for (j = n - 1 down to 1):
  if (a[j] > a[maxj]) then:
    maxj = j
  else:
    check if (j, maxj) is a better solution

复杂度:O(n)
C++ 实现:http://ideone.com/ENp5WR (实现使用整数数组，但 float 应该相同)