公司说全员降薪30%，我们不同意，打算集体罢工！结果第二天就我没去，领导在群里说你今天不来，以后也别来了！群里其他同事鸦雀无声

最近在刷算法题的时候，遇到了一道挺有意思的题目——两个子序列的最大点积。听起来像是个高大上的数学问题，但其实也不难。

简单来说，题目要求我们在给定的两个数组中，找到两个子序列（顺序可以打乱，但不可以改变元素），使得这两个子序列对应元素相乘后的点积最大。

这类问题一开始可能会让人觉得有点复杂，尤其是要考虑子序列的选择。毕竟，直接暴力解法不行，时间复杂度太高。我们要用点聪明的技巧来优化。首先，想一想，点积的公式是啥：

点积 = a1*b1 + a2*b2 + a3*b3 + ... + an*bn

也就是说，两个数组的对应元素要尽量大，点积才会大。那么，能不能通过某种方式，去“配对”数组中的元素，使得它们之间的乘积最大呢？

解题思路

直觉告诉我，点积要大，就得让大的数和大的数配对，小的数和小的数配对。比如说，如果数组 A = [1, 3, -5] 和 B = [4, -2, -1]，为了使得点积尽可能大，我们就得让最大的数3和4配对，负数-5和-1配对。类似这样，只有保证“同类相配”，才能发挥出点积的最大效果。

接下来，问题变成了如何选择两个数组的元素。最直接的做法就是把两个数组都排序，然后将排序后的元素逐个相乘，求和。

Python 实现

def maxDotProduct(A, B):
    # 对两个数组进行排序
    A.sort()
    B.sort()
        # 计算点积
    result = sum([a * b for a, b in zip(A, B)])
    return result

在这个解法中，首先对两个数组进行升序排序。然后通过 zip() 函数将两个数组一一配对，最后用列表推导式计算对应元素的乘积，并求和得到最终的点积。

这看起来是不是很简单？其实，就是将问题转化成了一个“最大配对”问题。通过排序，我们自动确保了最大的数配对最大的数，最小的数配对最小的数，负数也被合理地处理了。

更深一步的思考

这个方法有一个很明显的优势，就是排序的时间复杂度为 O(n log n)，然后计算点积的时间复杂度是 O(n)。所以总体时间复杂度是 O(n log n)，对于一般的题目来说，已经是一个很好的解法了。

但如果我们深究的话，还可以考虑一些边界情况。例如，数组中有重复的元素或者全是负数的情况。其实，对于负数的处理，排序依然是最有效的方式。毕竟，负负得正，负数在配对时的行为也可以通过排序得到合理的解释。

再来个优化？

虽然现在的解法已经很直观了，但我还是忍不住想问一个问题：能不能不排序呢？因为排序毕竟是有点“重”的操作，O(n log n) 的复杂度对于大数据量可能会有点捉襟见肘。

但是，仔细想想，除非我们做些额外的约束，不然排序其实是优化不掉的。毕竟要让大数配大数，排序几乎是唯一的可行方法。

虽然这个题目不是特别复杂，但它很好的展示了如何通过合理的排序和配对策略来简化问题，最大化解法的效率。如果遇到类似的题目，不妨先从排序着手，往往能找到意想不到的高效解法。