求数组中子数组元素和与最小值乘积最大的O(nlogn)算法

分治法的核心逻辑是分而治之：把数组拆分成子数组递归求解，再合并各部分结果。针对你的问题，具体实现思路如下：

1. 递归拆分与子问题求解 #

将当前处理的数组区间[left, right]从中间mid拆分为左半区[left, mid]和右半区[mid+1, right]，分别递归计算这两个子区间的最大乘积值，记为left_max和right_max。

2. 处理跨中间的子数组（关键步骤） #

递归拆分后，还需要考虑包含中间位置mid和mid+1的子数组——这类子数组的解不会被左右子问题覆盖，必须单独计算：

• 向左扩展：从mid出发向左遍历，维护当前子数组的元素和sum_left，以及当前子数组的最小值min_left。每移动一位就更新这两个变量，并计算sum_left * min_left，记录向左扩展过程中的最大值max_left。
• 向右扩展：从mid+1出发向右遍历，同理维护sum_right和min_right，计算并记录向右扩展的最大值max_right。
• 跨左右组合：还要考虑同时包含左右扩展部分的子数组，即把向左扩展的任意一个子数组和向右扩展的任意一个子数组拼接，计算(sum_left + sum_right) * min(min_left, min_right)，找出这类组合的最大值cross_combined_max。
• 跨中间的最终最大值是max(max_left, max_right, cross_combined_max)。

3. 合并结果 #

当前区间的最大乘积值取左子问题、右子问题、跨中间子数组这三者的最大值，即max(left_max, right_max, cross_max)，递归返回这个值直到处理完整个数组。

复杂度说明 #

每次递归将数组拆分为两个等长子数组，递归深度为O(logn)；每一层递归中，处理跨中间子数组的操作是线性时间O(n)（左右遍历总共覆盖整个区间）。因此整体时间复杂度为O(nlogn)，完全符合你的要求。

额外提示 #

由于数组元素全为正数，扩展子数组时元素和只会递增，而最小值只会保持不变或减小——这一特性让我们可以在遍历过程中高效维护sum和min变量，不需要额外的复杂计算。

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