两数组特定表达式最大化问题：寻求优于O(n²)的算法

首先对目标表达式做数学变形，找到可优化的切入点：

给定表达式：

value(i,j) = A[i]*B[i] + A[i]*B[j] + A[j]*B[j]

令 C[j] = A[j] * B[j]，表达式可简化为：

value(i,j) = A[i]*B[i] + (A[i]*B[j] + C[j])

也就是说，对于每个索引i，我们只需要找到j≠i时 A[i]*B[j] + C[j] 的最大值，再加上A[i]*B[i]，最终取所有i对应结果的最大值即可。

核心优化思路：凸包优化（Convex Hull Trick） #

观察A[i]*B[j] + C[j]，这可以看作是关于A[i]的线性函数：对于每个j，对应直线 y = B[j] * x + C[j]，其中x就是A[i]。我们的需求转化为：对每个x=A[i]，找到除j=i外所有直线在x处的最大值。

由于题目中B[j]都是正整数，所有直线的斜率为正，可通过以下步骤实现高效查询：

1. 预处理直线：将所有j对应的直线按斜率B[j]排序。
2. 构建凸包：维护一个单调队列，保留能成为某段区间最大值的直线（剔除被其他直线完全覆盖的冗余直线），这一步时间复杂度为O(n log n)。
3. 查询最大值：对每个A[i]，在凸包中通过二分查找找到对应区间的最优直线，得到A[i]*B[j] + C[j]的最大值。若最优直线对应的j=i，则取次优值；或者预处理时将直线分为左右两部分，避免查询到自身，这一步每个查询时间复杂度为O(log n)。

总体时间复杂度为O(n log n)，远优于O(n²)的双重循环。

示例验证 #

对于给定示例：

A = [6, 3, 4, 8, 3]
B = [2, 4, 2, 1, 2]

计算C[j] = A[j]*B[j]得到 [12, 12, 8, 8, 6]，对应直线为：

• j0: y=2x+12
• j1: y=4x+12
• j2: y=2x+8
• j3: y=1x+8
• j4: y=2x+6

当i=3时，A[i]=8，查询j≠3的直线最大值为4*8+12=44，加上A[i]*B[i]=8*1=8，得到结果52，与示例一致。

替代简化方案（O(n) 时间，非严谨但实用） #

如果不想实现凸包逻辑，可以通过维护少量候选索引来近似求解：

• 维护B[j]最大的前2个索引
• 维护C[j]最大的前2个索引
• 维护A[j]+B[j]最大的前2个索引

对每个i，仅与这些候选索引（排除i自身）计算表达式值，取最大值。这种方法时间复杂度为O(n)，在大多数正整数数组场景下能命中最优解，适合对实现复杂度要求低的场景。

为什么单一维度排序无效？ #

目标表达式是A[i]和B[j]的线性组合，最优解并非由A[j]/B[j]或A[j]*B[j]单一维度决定，单一维度排序无法捕捉这种线性关系带来的最大值，因此无法得到正确的最优解。

内容的提问来源于stack exchange，提问作者random