如何基于分治法实现O(n)时间复杂度的数组两数最大乘积算法？

数组中两数的最大乘积只会出自两种情况：要么是两个最大正数的乘积，要么是两个最小负数的乘积（负负得正可能远大于正数乘积）。你之前单独用findMax和findMin失败，是因为只抓全局极值不够——还需要第二大、第二小的元素，比如数组[-10,-9,-1]的最大乘积是-10*-9=90，但单独取全局最小和全局最大相乘得到的是10，完全不对。

分治法的思路是递归拆分数组，每个子问题返回四个关键值：当前子数组的最大值、第二大值、最小值、第二小值，同时返回该子数组内的最大两数乘积。合并时通过子数组的这些值计算所有可能的乘积情况，最终得到全局最大值。

具体实现步骤 #

1. 递归终止条件：
   • 子数组长度为1：最大值、最小值都是该元素，第二大设为负无穷，第二小设为正无穷，最大乘积设为负无穷（单个元素无法形成乘积）
   • 子数组长度为2：直接计算两个元素的最大、第二大、最小、第二小值，以及它们的乘积
2. 拆分与递归：将数组从中间拆分为左右两个子数组，分别递归处理
3. 合并结果：
   • 从左右子数组的四个极值中，筛选出当前数组的最大值、第二大值、最小值、第二小值
   • 计算所有可能的最大乘积候选：左右子数组各自的最大乘积、当前数组两个最大值的乘积、当前数组两个最小值的乘积、左右最大值的乘积、左右最小值的乘积，取其中最大的作为当前数组的最大乘积

Python代码实现 #

def max_two_product(arr):
    def split_and_merge(left, right):
        # 单个元素，无法形成乘积
        if left == right:
            return (arr[left], float('-inf'), arr[left], float('inf'), float('-inf'))
        # 两个元素，直接计算所有值
        if right - left == 1:
            a, b = arr[left], arr[right]
            top1, top2 = max(a,b), min(a,b)
            bot1, bot2 = min(a,b), max(a,b)
            prod = a * b
            return (top1, top2, bot1, bot2, prod)
        
        mid = (left + right) // 2
        # 递归处理左右子数组
        l_top1, l_top2, l_bot1, l_bot2, l_prod = split_and_merge(left, mid)
        r_top1, r_top2, r_bot1, r_bot2, r_prod = split_and_merge(mid+1, right)
        
        # 合并得到当前数组的前两大值
        all_max = sorted([l_top1, l_top2, r_top1, r_top2], reverse=True)
        curr_top1, curr_top2 = all_max[0], all_max[1]
        # 合并得到当前数组的前两小值
        all_min = sorted([l_bot1, l_bot2, r_bot1, r_bot2])
        curr_bot1, curr_bot2 = all_min[0], all_min[1]
        
        # 计算所有可能的乘积候选
        candidates = [
            l_prod, r_prod,
            curr_top1 * curr_top2,
            curr_bot1 * curr_bot2,
            l_top1 * r_top1,
            l_bot1 * r_bot1
        ]
        curr_prod = max(candidates)
        
        return (curr_top1, curr_top2, curr_bot1, curr_bot2, curr_prod)
    
    if len(arr) < 2:
        return None
    _, _, _, _, result = split_and_merge(0, len(arr)-1)
    return result

# 测试用例
print(max_two_product([3, -1, -2, 5]))  # 输出 15（3*5）
print(max_two_product([-5, -4, 3, 2]))  # 输出 20（-5*-4）
print(max_two_product([-10, -9, -1]))    # 输出 90（-10*-9）

时间复杂度说明 #

每次递归拆分数组为两半，合并操作仅处理固定数量的候选值（O(1)操作），整个递归过程中每个元素仅被访问一次，总时间复杂度为O(n)，符合你的要求。

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