如何求解整数数组中所有长度≥2区间的max·min乘积的最大值？

给定n个正整数a₁、a₂、…、aₙ，需找出所有满足1≤l<r≤n的整数对(l,r)对应的区间[aₗ, aₗ₊₁, …, aᵣ]的max(aₗ,…,aᵣ) × min(aₗ,…,aᵣ)的最大值。

输入说明 #

• 第一行输入测试用例数量t（1≤t≤10000）
• 每个测试用例第一行输入整数n（2≤n≤10⁵）
• 第二行输入n个整数a₁至aₙ（1≤aᵢ≤10⁶）
• 所有测试用例的n之和不超过3×10⁵

输出说明 #

针对每个测试用例，输出上述乘积的最大值。

示例 #

输入4组测试用例，对应输出分别为12、6、4761、381274500335。

核心结论：所求的最大乘积必然出现在某一对相邻元素的乘积中。

原因如下：
对于任意长度≥3的区间，设其最大值为M，最小值为m。若M和m相邻，则它们的乘积等于该区间的max*min；若M和m不相邻，二者之间至少存在一个元素x（m ≤ x ≤ M），此时M*x ≥ M*m（因x≥m>0），而M与x所在的相邻对（或更小的子区间）的乘积会大于原区间的max*min。因此，所有长度≥3的区间的max*min都不可能超过某一对相邻元素的乘积。

基于此，我们只需遍历数组，计算每一对相邻元素的乘积，取最大值即可。

以Python为例：

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    t = int(input[ptr])
    ptr += 1
    for _ in range(t):
        n = int(input[ptr])
        ptr += 1
        a = list(map(int, input[ptr:ptr+n]))
        ptr += n
        max_prod = 0
        for i in range(n-1):
            current_prod = a[i] * a[i+1]
            if current_prod > max_prod:
                max_prod = current_prod
        print(max_prod)

if __name__ == "__main__":
    main()

代码说明 #

• 使用sys.stdin.read()一次性读取所有输入，避免多次IO操作，提升处理大规模输入的效率。
• 遍历每个测试用例的数组，计算相邻元素乘积并维护最大值。
• 时间复杂度为O(sum n)，完全符合题目对时间性能的要求。

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