求内积最大的子数组

之前在网上看到有好多人在讨论这道题，据说是一道 Google 的面试题。

问题描述：有两个长度均为 n 的整数数组 A 和 B，现在要从这两个数组中各抽出 s 个数字，分别构成两个新的数组 C 和 D，要求数组 C 和 D 的内积最大。

用数学语言描述一下题目，就是已知：\(A=\left[a_1,a_2,\cdots,a_n\right]\)，\(B=\left[b_1,b_2,\cdots,b_n\right]\)；

求：\(C=\left[c_1,c_2,\cdots,c_s\right]\)，\(D=\left[d_1,d_2,\cdots,d_s\right]\)，满足：\(\forall c_i\in C,c_i\in A\)，\(\forall d_i\in D,d_i\in B\)；

要使得 C、D 的内积（\(C\cdot D=c_1d_1+c_2d_2+\dots+c_s d_s\)）最大。

一、先考虑只有正数的情况：

当 s = 1 时，题目就退化成，从 n 个正整数中选取一个，从另外 n 个正整数中选取一个，使得乘积最大。显然，两次选取的都应该是那些数中最大的。

当 s > 1 时，我们分两步考虑，先考虑选取哪些数，再考虑这些数怎么配对。

1. 相信很多人都可以轻松地得出这样的结论：从 A 中选取最大的 s 个数构成 C，从 B 中选取最大的 s 个数构成 D，才有可能使得 C、D 内积最大。因为如果用 A 中的某个较小的数替换 C 中的任何一个数字，都会导致对应的乘积变小，从而整个内积变小。对于 D 也是类似的。
2. 对于选定的 C 和 D，如何配对呢？显然，应该让 C 中最大的数与 D 中最大的数相乘，C 中第二大的数与 D 中第二大的数相乘，以此类推。这个命题的证明也是很简单的，考虑任意两对数字：\(c_i\leq c_j\)，\(d_k\leq d_l\)，显然有

因此，如果 A、B 全部都是正整数，那只需要分别排序后，从大到小选取 s 个数即可。

二、接下来考虑只有负数的情况：

只有负数跟只有正数是类似的，因为两个负数相乘的结果与这两个负数的绝对值相乘是一样的。根据上面的分析，我们只要对 A、B 分别排序后，从小到大（即绝对值从大到小）选取 s 个数即可。

三、再考虑两个数组一个全是正数，另一个全是负数的情况：

不妨设 A 中全是正数，B 中全是负数。

当 s = 1 时，题目就退化成，从 n 个正整数中选取一个，从另外 n 个负整数中选取一个，使得乘积最大。显然，两次选取的都应该是那些数中绝对值最小的（即最小的正数和最大的负数）。

当 s > 1 时，还是分两步考虑。

1. 很容易证明，应该从两个数组中分别选取绝对值最小的 s 个数（即正数数组中最小的 s 个数，负数数组中最大的 s 个数）。因为如果剩余的任何数字替换进来，都会导致对应的乘积的绝对值变大，乘积本身变小，从而整个内积变小。值得注意的是，很多人在这里容易出错，他们没有考虑到乘积为负数时，绝对值越大，乘积本身越小。
2. 对于选定的 C 和 D，如何配对呢？根据上面的式子 \(\ref{eq}\) 可以知道，我们还是要让最大的那对数相乘，第二大的那对数相乘，……。这里需要注意，也是很多人容易出错的地方，最大的那对数是正数中的最大值（绝对值也最大）和负数中的最大值（绝对值最小）。与全是正数时不同的一点是，两个数组都是正数时，最大的那对数的乘积恰好也是最大的；但一正一负的时候，最大的那对数的乘积并不一定是最大，最小的一对数的乘积也不一定是最小，但他们累加起来一定是最大的。比如 [1, 2] 和[-1, -2]，正确的配对应该是 2 * -1 + 1 * -2 = -4，而不是 1 * -1 + 2 * -2 = -5。

四、几种特殊情况都考虑完了，最后就是正负数任意混合的一般情况。根据上面的分析，我们终归是要对 A 和 B 分别排序的，排序之后将两个数组的下标对齐，可以将两个数组分成三个部分，第一个部分中两个的数组元素都是负数（负数部分），第二个部分中一个数组元素都是负数而另一个都是正数（异号部分），第三个部分中两个数组的元素都是正数（正数部分），如下所示：

由于负数部分和正数部分都产生正的乘积，我们需要同时考虑这两个部分。每次从这两个部分各选出绝对值最大的一对数，将乘积更大的那对从 A、B 中转移到 C、D 中，然后继续比较。

如果负数部分和正数部分都取完了，还缺 m 对数，那就从异号部分选取最小的 m 个正数，和最大的 m 个负数，对应配对即可。

算法示意：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def MinInnerProduct(A, B, n, s):
  if not len(A) == len(B) == n or not 0 <= s <= n:
    raise Exception('Invalid arguments.')

  A.sort()
  B.sort()
  (C, D, sum) = ([], [], 0)
  (i, j) = (0, n - 1)

  while len(C) < s:
    val1 = A[i] * B[i]
    val2 = A[j] * B[j]
    if val1 < 0 and val2 < 0:
      break
    if val1 >= val2:
      C.append(A[i])
      D.append(B[i])
      sum += val1
      i += 1
    else:
      C.append(A[j])
      D.append(B[j])
      sum += val2
      j -= 1

  j -= s - len(C) - 1
  while len(C) < s:
    C.append(A[i])
    D.append(B[j])
    sum += A[i] * B[j]
    i += 1
    j += 1

  return (C, D, sum)

算法的空间复杂度为 O(s)，即用来存储 C、D 的空间；时间复杂度为 O(n log n)。

============ 并不华丽的分割线 ============

最后说个题外的事情。这是最后一篇从以前“钟磬居”网站备份回来的算法文章了。当年的钟磬居有如昙花一现，好多文章都只存在于 Google Reader 的缓存中了。让我没想到的是，刚才搜一个东西的时候，搜索结果第一条竟然是这篇文章。当然不是你看到的这一篇，而是之前发在钟磬居中被转载出去的。一字不差啊，连我加的粗体都还在，也保留了我当时文章中的一个错误（这里已经修正）。当时的钟磬居跟现在的 GoCalf 一样，看的人不算太少，但没有人评论。想起中学时喜欢的一句话“纵是昙花一现，也有一个月下赏花人，应无所憾”。送给逝去的钟磬居，鼓励一下自己。继续努力。

再次强调，本文不是转载，是原文，是从已经关闭了的网站中恢复回来的原文。GoCalf 网站中，如无特殊说明，一律原创。

Like this post? Share on: Twitter ❄ Facebook ❄ Email