给定等长正整数数组a、b，求i≠j时目标函数最大值的亚二次时间算法

问题分析与表达式化简 #

首先我们先对目标函数做等价变形，简化求解逻辑：
目标要求的最大值为：
max(a[i]*b[i] + a[i] * b[j] + a[j] * b[j], a[i]*b[i] + a[j] * b[i] + a[j] * b[j])
我们可以把两个表达式的公共项提取出来，得到：
max_val = a[i]b[i] + a[j]b[j] + max(a[i]b[j], a[j]b[i])
进一步拆分可以得到两个独立的待最大化分支：

• 分支1：a[i]*(b[i] + b[j]) + a[j]b[j]，等价于对每个j，求max_{i≠j}(a[i] * b[j] + a[i]b[i]) + a[j]b[j]
• 分支2：a[j]*(b[i] + b[j]) + a[i]b[i]，等价于对每个j，求max_{i≠j}(b[i] * a[j] + a[i]b[i]) + a[j]b[j]

低于二次时间复杂度的算法实现 #

两个分支的求解逻辑完全一致，都是典型的线性函数最大值查询问题，可以用凸包优化（Convex Hull Trick, CHT）离线处理：

• 对于分支1，每个下标i对应一条线性函数：y = a[i] * x + a[i]b[i]，我们需要对每个j，查询所有i≠j的函数在x = b[j]处的最大值
• 对于分支2，每个下标i对应一条线性函数：y = b[i] * x + a[i]b[i]，我们需要对每个j，查询所有i≠j的函数在x = a[j]处的最大值

具体实现步骤：

1. 把所有线性函数和查询点按x值（分支1为b[j]，分支2为a[j]）离线排序
2. 用单调队列维护凸包的对应边界，按顺序处理所有查询，每个查询可以在均摊O(1)时间内得到最大值
3. 如果最大值对应的i刚好等于j，取次大值即可（可以提前存储每个查询点的前2-3个候选值解决冲突）
4. 两个分支的所有查询结果的最大值就是目标函数的最大值，同时可以记录对应的下标i、j

复杂度说明 #

无论是只需要求解最大值，还是需要同时找到对应的下标i和j，都可以在O(n log n) 时间复杂度内完成，远低于O(n²)的二次复杂度。如果数组的a[i]或b[i]本身满足单调性，可以进一步优化到O(n)时间复杂度。

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