最大乘积子数组（进阶版：允许一次翻转某个子数组）
字数 8436 2025-12-13 10:20:18

最大乘积子数组（进阶版：允许一次翻转某个子数组）

题目描述
给定一个整数数组 nums，可以最多翻转数组的任意一个连续子数组一次（即反转该子数组的顺序）。翻转后，返回可能得到的最大子数组乘积。子数组是原始数组的一个连续子序列。数组中的整数可以是正数、负数或零。

示例：
输入：nums = [2,3,-2,4,-1]
解释：不翻转时，最大子数组乘积是 23=6。但我们可以翻转子数组[-2,4,-1]得到[-1,4,-2]，此时数组变为[2,3,-1,4,-2]，最大子数组乘积是3 -1 * 4 * -2 = 24。
输出：24

解题过程循序渐进讲解

这个问题是在经典“最大乘积子数组”基础上的一个增强变体。核心挑战在于如何将“一次翻转”的操作融入动态规划的状态设计中。我们逐步分析：

步骤1：回顾基础问题（最大乘积子数组）

经典问题（LeetCode 152）中，我们定义两个DP数组：

  • max_dp[i]：以 nums[i] 结尾的子数组的最大乘积。
  • min_dp[i]：以 nums[i] 结尾的子数组的最小乘积（用于处理负数相乘得正的情况）。

转移方程：

\[\begin{aligned} \text{max\_dp}[i] &= \max(\text{nums}[i],\ \text{max\_dp}[i-1] \times \text{nums}[i],\ \text{min\_dp}[i-1] \times \text{nums}[i]) \\ \text{min\_dp}[i] &= \min(\text{nums}[i],\ \text{max\_dp}[i-1] \times \text{nums}[i],\ \text{min\_dp}[i-1] \times \text{nums}[i]) \end{aligned} \]

最终答案即所有 max_dp[i] 中的最大值。
时间复杂度 O(n)，空间可优化到 O(1)。

步骤2：理解“翻转一个子数组”的影响

翻转一个子数组 nums[l..r] 会改变元素顺序，相当于反转了这一段中连续乘积的“方向”。
例如原数组 [A, B, C, D]，翻转 B,C 得到 [A, C, B, D]，那么原来以 C 结尾的乘积在翻转后可能变成以 B 结尾（方向反了）。

关键观察：
任意翻转一段子数组，相当于从原数组中选取三个连续段：前缀 + 反转段 + 后缀，其中反转段内部顺序倒置。
我们要找的就是一种分割方式，使某个子数组乘积最大，这个子数组可能：

  1. 完全不经过翻转段（即经典问题的答案）。
  2. 完全在翻转段内部（但顺序反了，乘积和原来一样，因为乘法满足交换律，所以这种情况等价于经典问题，无需特殊处理）。
  3. 跨越翻转段的边界：这是翻转带来新可能性的地方。例如子数组一部分在反转段前，一部分在反转段后，中间是反转段的一部分但顺序颠倒。

步骤3：将问题转化为“拼接乘积”

考虑翻转子数组 nums[l..r]。
设我们要计算的子数组起始在 i，结束在 j，且它们跨越翻转段的边界。实际上，翻转后，原来顺序 nums[i..j] 可能被拆成两段乘积的拼接。

更直观的方法：
将原数组分成三部分：Left, Mid, Right。翻转 Mid 后，新数组是 Left + reversed(Mid) + Right。
在新数组中，一个子数组可能是：

  • 在 Left 内部
  • 在 reversed(Mid) 内部
  • 在 Right 内部
  • 跨越 Left 和 reversed(Mid) 的连接处
  • 跨越 reversed(Mid) 和 Right 的连接处
  • 跨越 Left, reversed(Mid), Right 三部分

由于 reversed(Mid) 内部乘积和原 Mid 乘积一样（乘法交换律），唯一不同是连接处的乘积顺序变化。
所以，我们只需要考虑连接处。

步骤4：定义状态以处理翻转

一个巧妙的方法：
定义四个数组，分别表示从某个方向计算的连续乘积：

  1. prefix_max[i]：从数组开头到 i 的某个连续子数组（以 i 为结尾）的最大乘积（即经典问题从左到右的 max_dp）。
  2. prefix_min[i]：从开头到 i 的连续子数组（以 i 为结尾）的最小乘积。
  3. suffix_max[i]：从数组末尾到 i 的某个连续子数组（以 i 为起点）的最大乘积（即从右到左计算的类似 DP）。
  4. suffix_min[i]：从末尾到 i 的连续子数组（以 i 为起点）的最小乘积。

如何计算 suffix_* 数组？
我们从右往左扫描，定义：

  • suffix_max[i] 表示从 i 开始往右的连续子数组（以 i 为起点）的最大乘积。
  • 类似地，suffix_min[i] 是最小乘积。

递推（从右到左，j 从 n-1 到 0）：

\[\begin{aligned} \text{if } j = n-1: & \quad \text{suffix\_max}[j] = \text{suffix\_min}[j] = nums[j] \\ \text{else}: & \quad \text{suffix\_max}[j] = \max(nums[j],\ nums[j] \times \text{suffix\_max}[j+1],\ nums[j] \times \text{suffix\_min}[j+1]) \\ & \quad \text{suffix\_min}[j] = \min(nums[j],\ nums[j] \times \text{suffix\_max}[j+1],\ nums[j] \times \text{suffix\_min}[j+1]) \end{aligned} \]

步骤5：利用状态计算翻转带来的新乘积

翻转子数组 nums[l..r] 后，数组变为：
nums[0..l-1] + reverse(nums[l..r]) + nums[r+1..n-1]。

考虑一个跨越 l-1 和 l 边界的子数组（即包含 l-1 和翻转段的开头部分）：
翻转前，这个子数组是 nums[k..l-1] 和 nums[l..m] 的乘积，但翻转后，nums[l..m] 在 reversed 段中变成了 nums[r - (m-l) .. r] 的顺序，不直观。

但我们可以这样想：
翻转后，原来的 nums[l..r] 顺序反了，原来位于 l 的元素现在在 r 位置。
所以，翻转后跨越边界的子数组，相当于在原数组中选取两段不连续的部分，它们的乘积相乘，但这两段在原数组中是“背靠背”方向相反的。

具体来说，翻转后，新数组在位置 l-1 之后的元素是原 nums[r]。
所以，跨越边界的一个子数组（在原数组中是 i..j 且 i <= l-1 < r <= j）的乘积，可以看作：

  • 在原数组中以 l-1 结尾的某段最大/最小乘积（来自 prefix_*[l-1]）
  • 乘以
  • 在原数组中以 r 开始的某段最大/最小乘积（来自 suffix_*[r]）

因为翻转后，两段在边界处是原数组的 l-1 位置和 r 位置直接相连。

因此，对于每个可能的边界 (l-1, r)，其中 l <= r，翻转子数组 l..r 后，新数组在边界处能得到的最大乘积候选为：

\[\max( \text{prefix\_max}[l-1] \times \text{suffix\_max}[r],\ \text{prefix\_min}[l-1] \times \text{suffix\_min}[r] ) \]

但注意，l-1 可能不存在（l=0），则前半段为空，乘积为 1（但子数组不能为空，所以我们只考虑 l>=1 的情况，或者前半段为空时，只取后半段）。

同理，我们也要考虑边界 (r, r+1) 的跨越情况，但对称，可以统一处理。

步骤6：统一公式

我们可以枚举所有可能的“分界点”p，将数组看作 A = nums[0..p] 和 B = nums[p+1..n-1]，然后考虑翻转 A 的某个后缀和 B 的某个前缀组成的一段，但这样复杂。

更直接枚举法：
枚举所有可能的翻转区间 [l, r]，然后计算翻转后整个数组的最大子数组乘积。但这样 O(n³) 太慢。

优化：
我们只需要考虑翻转后，那些跨越原数组某个位置 p 和 p+1 的子数组，其中 p 是翻转区间的左边界-1 或右边界。

实际上，可以证明：翻转后能获得的最大子数组乘积，一定是以某个位置 p 为“缝合点”，将原数组的两段乘积（一段以 p 结尾，一段以 p+1 开头）相乘得到。
这是因为翻转操作相当于将两段不连续的乘积“粘合”在一起，粘合点就是 p 和 p+1 在原数组的位置。

所以，我们枚举每个可能的 p（0 <= p < n-1），然后考虑翻转子数组 [p+1, r] 或 [l, p] 等等，但最终等价于计算：

\[\text{candidate} = \max\{ \text{prefix\_max}[p] \times \text{suffix\_max}[p+1],\ \text{prefix\_min}[p] \times \text{suffix\_min}[p+1] \} \]

然后，我们还需要考虑这两段各自的符号，有可能负负得正，所以上面取了最大和最小两种可能。

步骤7：最终算法步骤

  1. 计算 prefix_max[i], prefix_min[i] 从左到右。
  2. 计算 suffix_max[i], suffix_min[i] 从右到左。
  3. 初始化答案 ans 为经典最大子数组乘积（即不翻转的情况），就是 max(prefix_max) 和 max(suffix_max) 的较大者。
  4. 对于每个位置 p = 0 到 n-2：
    • 计算 candidate1 = prefix_max[p] * suffix_max[p+1]
    • 计算 candidate2 = prefix_min[p] * suffix_min[p+1]
    • 更新 ans = max(ans, candidate1, candidate2)
  5. 返回 ans。

注意：如果某一段为空（比如 p 是 -1 或 n-1），那么乘积等于另一段的值，但我们的枚举已经包含在不翻转的情况中。

步骤8：边界和细节

  • 当数组长度<=1，翻转无意义，答案就是唯一元素。
  • 乘法涉及整数，注意乘积可能溢出（题目一般用 32 位整数，但乘积可能超过 32 位，可用 64 位存储）。
  • 当 p 不存在时（n=1）跳过枚举。

步骤9：举例验证

nums = [2,3,-2,4,-1]

计算 prefix_max = [2,6,-2,4,-4]（实际是每个位置结尾的最大乘积）
经典最大乘积是 6。

suffix_max 从右到左：

  • 初始化：i=4: -1
  • i=3: max(4, 4×-1= -4) → 4
  • i=2: max(-2, -2×4=-8, -2×-1=2) → 2
  • i=1: max(3, 3×2=6, 3×-4=-12) → 6
  • i=0: max(2, 2×6=12, 2×-8=-16) → 12
    所以 suffix_max = [12,6,2,4,-1]

枚举 p：

  • p=0: max(26=12, 26=12) → 12
  • p=1: max(62=12, -12 -4=48) → 48
  • p=2: max(-24=-8, -24=-8) → -8
  • p=3: max(4*-1=-4, 4*-1=-4) → -4

最大 candidate 是 48，但注意 48 来自 prefix_min[1]=-12 和 suffix_min[2]=-4 乘积 48。
检查是否可能：
p=1 对应原数组分割 [2,3] 和 [-2,4,-1]，翻转区间是 [p+1, r] 即 [2,4]，翻转后数组 [2,3,-1,4,-2]，此时最大子数组乘积是 3*-14-2=24，不是 48。
说明我们的 candidate 48 是无效的，因为 prefix_min[1]=-12 对应的子数组是 [2,3,-2]？等等，我们算一下：

prefix_min[1] 是到下标 1 结尾的最小子数组乘积：
prefix_min[1] = min(3, 23=6, 23=6) 不对，经典递推：
i=0: (2,2)
i=1: max(3, 23=6, 23=6)=6, min(3, 23=6, 23=6)=3? 错！
重算：

i=0: max=2, min=2
i=1: 候选(3, 23=6, 23=6) → max=6, min=3（因为3更小） 对。
所以 prefix_min[1]=3 不是 -12。

我们发现之前的 suffix_min 算错了。我们来正确计算。

正确计算 suffix_min：
i=4: suffix_max[4]=-1, suffix_min[4]=-1
i=3: 候选(4, 4×-1=-4, 4×-1=-4) → max=4, min=-4
i=2: 候选(-2, -2×4=-8, -2×-4=8) → max=8, min=-8
i=1: 候选(3, 3×8=24, 3×-8=-24) → max=24, min=-24
i=0: 候选(2, 2×24=48, 2×-24=-48) → max=48, min=-48

所以 suffix_max = [48,24,8,4,-1], suffix_min = [-48,-24,-8,-4,-1]
prefix_max = [2,6,-2,4,-4], prefix_min=[2,3,-12,-48,48]（这里我快速递推：
i=0: (2,2)
i=1: max(3,6,6)=6, min(3,6,6)=3
i=2: max(-2,6*-2=-12,3*-2=-6) = -2, min(-2,-12,-6)=-12
i=3: max(4,-24=-8,-124=-48)=4, min(4,-8,-48)=-48
i=4: max(-1,4*-1=-4,-48*-1=48)=48, min(-1,-4,48)=-4
所以 prefix_min=[2,3,-12,-48,-4] 注意最后是 -4，不是 48 我写错了。修正：
i=4: 候选(-1, 4*-1=-4, -48*-1=48) → max=48, min=-4 对，所以 prefix_min[4] = -4。

现在枚举 p：
p=0: max(224=48, 2-24=-48) → 48
p=1: max(68=48, 3-8=-24) → 48
p=2: max(-24=-8, -12-4=48) → 48
p=3: max(4*-1=-4, -48*-1=48) → 48

所以多个 p 得到 48。但 48 可能吗？
p=2: prefix_min[2] = -12 对应子数组 [2,3,-2] 乘积 -12，suffix_min[3] = -4 对应子数组 [4,-1] 乘积 -4，相乘 (-12)(-4)=48。
这在翻转后对应什么？p=2 对应原数组分割 [0..2] 和 [3..4]，翻转区间是 [p+1, r] 即 [3,4]，翻转后数组 [2,3,-2, -1,4]。最大子数组乘积是 3-2*-1*4=24，不是 48。
所以候选 48 并不对应实际的一个子数组，因为 prefix_min[2] 和 suffix_min[3] 对应的子数组在原数组中不相邻，翻转后也不能连成一段（因为中间隔了未翻转部分）。

这说明我们的枚举方法有缺陷。实际上，我们枚举 p 时，必须确保两段在原数组中相邻，翻转其中一段后它们才能连起来。我们的公式错误地允许了任意两段相乘。

步骤10：修正方法

正确方法：枚举翻转区间 [l,r]，然后计算新数组的最大子数组乘积，但这样 O(n³)。优化：
我们可以用 O(n²) 的时间枚举所有区间，对每个区间翻转，用类似最大子数组乘积的方法 O(n) 计算，总体 O(n³) 仍大。

但注意到，翻转区间 [l,r] 后，最大子数组要么完全在翻转区间内（同原数组），要么跨越边界。跨越边界时，一定是原数组中以 l-1 结尾的某段和以 r+1 开头的某段，加上整个翻转区间，因为翻转区间是整体反转，它的最大/最小乘积可以预处理。

定义：

  • max_prod_from[i] = 从 i 开始的最大连续乘积（类似 suffix_max 但必须从 i 开始）
  • min_prod_from[i]
  • max_prod_to[i] = 以 i 结尾的最大连续乘积（prefix_max[i]）

然后翻转区间 [l,r] 后，新数组的最大子数组乘积候选为：

  1. 完全在左边：max_prod_to[l-1]
  2. 完全在右边：max_prod_from[r+1]
  3. 跨越左边和翻转区间：max{ max_prod_to[l-1] * max_prod_rev, min_prod_to[l-1] * min_prod_rev } 等，其中 max_prod_rev 是翻转区间的最大连续乘积（等于原区间从 r 到 l 的方向计算，可以用类似 suffix/prefix 的方法得到）。
  4. 跨越翻转区间和右边：类似。

这样，如果我们预处理出每个区间的正反方向最大最小乘积，就可以 O(1) 计算每个翻转区间的结果。但预处理所有区间是 O(n²)，加上枚举区间 O(n²)，总体 O(n²) 可行。

由于时间关系，我们给出最终 O(n²) 的算法步骤（适用于 n 不太大时）：

  1. 预处理原数组的 prefix_max, prefix_min, suffix_max, suffix_min。
  2. 预处理 rev_max[l][r] 和 rev_min[l][r] 表示原数组区间 [l,r] 反转后的最大/最小连续乘积（从右到左计算，等价于从 r 到 l 的正向计算，可以用类似 suffix 的方法在 O(n²) 内算出）。
  3. 初始答案 = 经典最大子数组乘积。
  4. 枚举所有可能的翻转区间 [l,r]（0 <= l <= r < n）：
    • 不跨越边界的情况已在经典答案中。
    • 跨越左边和翻转区间：如果 l>0，计算候选 = 最优组合(prefix_max[l-1], prefix_min[l-1], rev_max[l][r], rev_min[l][r])，即四种乘法的最大值。
    • 跨越翻转区间和右边：如果 r<n-1，计算候选 = 最优组合(rev_max[l][r], rev_min[l][r], suffix_max[r+1], suffix_min[r+1])。
    • 跨越左、翻转、右三部分：如果 l>0 且 r<n-1，候选 = 最优组合(prefix_max[l-1], prefix_min[l-1], rev_max[l][r], rev_min[l][r], suffix_max[r+1], suffix_min[r+1])，即八种乘法的最大值。
  5. 更新全局最大值。

这个算法是 O(n²)，在 n <= 200 时可行。对于更大 n，可能有 O(n) 的解法，但更复杂，需进一步推导。

总结
本题核心在于理解翻转操作如何改变连续乘积的拼接方式，并通过预处理各个方向的最大最小乘积，枚举翻转区间来求得可能的最大乘积。由于完整 O(n) 解法较复杂，这里给出了 O(n²) 的可行思路。你可以先实现 O(n²) 版本，再尝试优化。

最大乘积子数组（进阶版：允许一次翻转某个子数组） 题目描述 给定一个整数数组 nums ，可以最多翻转数组的任意一个连续子数组一次（即反转该子数组的顺序）。翻转后，返回可能得到的最大子数组乘积。子数组是原始数组的一个连续子序列。数组中的整数可以是正数、负数或零。 示例： 输入：nums = [ 2,3,-2,4,-1 ] 解释：不翻转时，最大子数组乘积是 2 3=6。但我们可以翻转子数组[ -2,4,-1]得到[ -1,4,-2]，此时数组变为[ 2,3,-1,4,-2]，最大子数组乘积是3 -1 * 4 * -2 = 24。 输出：24 解题过程循序渐进讲解 这个问题是在经典“最大乘积子数组”基础上的一个增强变体。核心挑战在于如何将“一次翻转”的操作融入动态规划的状态设计中。我们逐步分析： 步骤1：回顾基础问题（最大乘积子数组） 经典问题（LeetCode 152）中，我们定义两个DP数组： max_dp[i] ：以 nums[i] 结尾的子数组的最大乘积。 min_dp[i] ：以 nums[i] 结尾的子数组的最小乘积（用于处理负数相乘得正的情况）。 转移方程： \[ \begin{aligned} \text{max\_dp}[ i] &= \max(\text{nums}[ i],\ \text{max\_dp}[ i-1] \times \text{nums}[ i],\ \text{min\_dp}[ i-1] \times \text{nums}[ i ]) \\ \text{min\_dp}[ i] &= \min(\text{nums}[ i],\ \text{max\_dp}[ i-1] \times \text{nums}[ i],\ \text{min\_dp}[ i-1] \times \text{nums}[ i ]) \end{aligned} \] 最终答案即所有 max_dp[i] 中的最大值。 时间复杂度 O(n)，空间可优化到 O(1)。 步骤2：理解“翻转一个子数组”的影响 翻转一个子数组 nums[l..r] 会改变元素顺序，相当于反转了这一段中连续乘积的“方向”。 例如原数组 [A, B, C, D] ，翻转 B,C 得到 [A, C, B, D] ，那么原来以 C 结尾的乘积在翻转后可能变成以 B 结尾（方向反了）。 关键观察： 任意翻转一段子数组，相当于从原数组中选取三个连续段： 前缀 + 反转段 + 后缀 ，其中反转段内部顺序倒置。 我们要找的就是一种分割方式，使某个子数组乘积最大，这个子数组可能： 完全不经过翻转段（即经典问题的答案）。 完全在翻转段内部（但顺序反了，乘积和原来一样，因为乘法满足交换律，所以这种情况等价于经典问题，无需特殊处理）。 跨越翻转段的边界 ：这是翻转带来新可能性的地方。例如子数组一部分在反转段前，一部分在反转段后，中间是反转段的一部分但顺序颠倒。 步骤3：将问题转化为“拼接乘积” 考虑翻转子数组 nums[l..r] 。 设我们要计算的子数组起始在 i ，结束在 j ，且它们跨越翻转段的边界。实际上，翻转后，原来顺序 nums[i..j] 可能被拆成两段乘积的拼接。 更直观的方法： 将原数组分成三部分： Left, Mid, Right 。翻转 Mid 后，新数组是 Left + reversed(Mid) + Right 。 在新数组中，一个子数组可能是： 在 Left 内部 在 reversed(Mid) 内部 在 Right 内部 跨越 Left 和 reversed(Mid) 的连接处 跨越 reversed(Mid) 和 Right 的连接处 跨越 Left, reversed(Mid), Right 三部分 由于 reversed(Mid) 内部乘积和原 Mid 乘积一样（乘法交换律），唯一不同是 连接处的乘积顺序变化 。 所以，我们只需要考虑连接处。 步骤4：定义状态以处理翻转 一个巧妙的方法： 定义四个数组，分别表示从某个方向计算的连续乘积： prefix_max[i] ：从数组 开头到 i 的某个连续子数组（以 i 为结尾）的最大乘积（即经典问题从左到右的 max_dp ）。 prefix_min[i] ：从开头到 i 的连续子数组（以 i 为结尾）的最小乘积。 suffix_max[i] ：从数组 末尾到 i 的某个连续子数组（以 i 为起点）的最大乘积（即从右到左计算的类似 DP）。 suffix_min[i] ：从末尾到 i 的连续子数组（以 i 为起点）的最小乘积。 如何计算 suffix_* 数组？ 我们从右往左扫描，定义： suffix_max[i] 表示从 i 开始往右的连续子数组（以 i 为起点）的最大乘积。 类似地， suffix_min[i] 是最小乘积。 递推（从右到左，j 从 n-1 到 0）： \[ \begin{aligned} \text{if } j = n-1: & \quad \text{suffix\_max}[ j] = \text{suffix\_min}[ j] = nums[ j ] \\ \text{else}: & \quad \text{suffix\_max}[ j] = \max(nums[ j],\ nums[ j] \times \text{suffix\_max}[ j+1],\ nums[ j] \times \text{suffix\_min}[ j+1 ]) \\ & \quad \text{suffix\_min}[ j] = \min(nums[ j],\ nums[ j] \times \text{suffix\_max}[ j+1],\ nums[ j] \times \text{suffix\_min}[ j+1 ]) \end{aligned} \] 步骤5：利用状态计算翻转带来的新乘积 翻转子数组 nums[l..r] 后，数组变为： nums[0..l-1] + reverse(nums[l..r]) + nums[r+1..n-1] 。 考虑一个跨越 l-1 和 l 边界的子数组（即包含 l-1 和翻转段的开头部分）： 翻转前，这个子数组是 nums[k..l-1] 和 nums[l..m] 的乘积，但翻转后， nums[l..m] 在 reversed 段中变成了 nums[r - (m-l) .. r] 的顺序，不直观。 但我们可以这样想： 翻转后，原来的 nums[l..r] 顺序反了，原来位于 l 的元素现在在 r 位置。 所以，翻转后跨越边界的子数组，相当于在原数组中选取两段不连续的部分，它们的乘积相乘，但这两段在原数组中是“背靠背”方向相反的。 具体来说，翻转后，新数组在位置 l-1 之后的元素是原 nums[ r ]。 所以，跨越边界的一个子数组（在原数组中是 i..j 且 i <= l-1 < r <= j）的乘积，可以看作： 在原数组中以 l-1 结尾的某段最大/最小乘积（来自 prefix_* [ l-1 ]） 乘以 在原数组中以 r 开始的某段最大/最小乘积（来自 suffix_* [ r ]） 因为翻转后，两段在边界处是原数组的 l-1 位置和 r 位置直接相连。 因此，对于每个可能的边界 (l-1, r)，其中 l <= r，翻转子数组 l..r 后，新数组在边界处能得到的最大乘积候选为： \[ \max( \text{prefix\_max}[ l-1] \times \text{suffix\_max}[ r ],\ \text{prefix\_min}[ l-1] \times \text{suffix\_min}[ r ] ) \] 但注意，l-1 可能不存在（l=0），则前半段为空，乘积为 1（但子数组不能为空，所以我们只考虑 l>=1 的情况，或者前半段为空时，只取后半段）。 同理，我们也要考虑边界 (r, r+1) 的跨越情况，但对称，可以统一处理。 步骤6：统一公式 我们可以枚举所有可能的“分界点”p，将数组看作 A = nums[0..p] 和 B = nums[p+1..n-1] ，然后考虑翻转 A 的某个后缀和 B 的某个前缀组成的一段，但这样复杂。 更直接枚举法： 枚举所有可能的翻转区间 [ l, r ]，然后计算翻转后整个数组的最大子数组乘积。但这样 O(n³) 太慢。 优化 ： 我们只需要考虑翻转后，那些跨越原数组某个位置 p 和 p+1 的子数组，其中 p 是翻转区间的左边界-1 或右边界。 实际上，可以证明： 翻转后能获得的最大子数组乘积，一定是以某个位置 p 为“缝合点”，将原数组的两段乘积（一段以 p 结尾，一段以 p+1 开头）相乘得到 。 这是因为翻转操作相当于将两段不连续的乘积“粘合”在一起，粘合点就是 p 和 p+1 在原数组的位置。 所以，我们枚举每个可能的 p（0 <= p < n-1），然后考虑翻转子数组 [ p+1, r] 或 [ l, p ] 等等，但最终等价于计算： \[ \text{candidate} = \max\{ \text{prefix\_max}[ p] \times \text{suffix\_max}[ p+1 ],\ \text{prefix\_min}[ p] \times \text{suffix\_min}[ p+1 ] \} \] 然后，我们还需要考虑这两段各自的符号，有可能负负得正，所以上面取了最大和最小两种可能。 步骤7：最终算法步骤 计算 prefix_max[i] , prefix_min[i] 从左到右。 计算 suffix_max[i] , suffix_min[i] 从右到左。 初始化答案 ans 为经典最大子数组乘积（即不翻转的情况），就是 max(prefix_ max) 和 max(suffix_ max) 的较大者。 对于每个位置 p = 0 到 n-2： 计算 candidate1 = prefix_ max[ p] * suffix_ max[ p+1 ] 计算 candidate2 = prefix_ min[ p] * suffix_ min[ p+1 ] 更新 ans = max(ans, candidate1, candidate2) 返回 ans。 注意：如果某一段为空（比如 p 是 -1 或 n-1），那么乘积等于另一段的值，但我们的枚举已经包含在不翻转的情况中。 步骤8：边界和细节 当数组长度 <=1，翻转无意义，答案就是唯一元素。 乘法涉及整数，注意乘积可能溢出（题目一般用 32 位整数，但乘积可能超过 32 位，可用 64 位存储）。 当 p 不存在时（n=1）跳过枚举。 步骤9：举例验证 nums = [ 2,3,-2,4,-1 ] 计算 prefix_ max = [ 2,6,-2,4,-4 ]（实际是每个位置结尾的最大乘积） 经典最大乘积是 6。 suffix_ max 从右到左： 初始化：i=4: -1 i=3: max(4, 4×-1= -4) → 4 i=2: max(-2, -2×4=-8, -2×-1=2) → 2 i=1: max(3, 3×2=6, 3×-4=-12) → 6 i=0: max(2, 2×6=12, 2×-8=-16) → 12 所以 suffix_ max = [ 12,6,2,4,-1 ] 枚举 p： p=0: max(2 6=12, 2 6=12) → 12 p=1: max(6 2=12, -12 -4=48) → 48 p=2: max(-2 4=-8, -2 4=-8) → -8 p=3: max(4* -1=-4, 4* -1=-4) → -4 最大 candidate 是 48，但注意 48 来自 prefix_ min[ 1]=-12 和 suffix_ min[ 2 ]=-4 乘积 48。 检查是否可能： p=1 对应原数组分割 [ 2,3] 和 [ -2,4,-1]，翻转区间是 [ p+1, r] 即 [ 2,4]，翻转后数组 [ 2,3,-1,4,-2]，此时最大子数组乘积是 3* -1 4 -2=24，不是 48。 说明我们的 candidate 48 是无效的，因为 prefix_ min[ 1]=-12 对应的子数组是 [ 2,3,-2 ]？等等，我们算一下： prefix_ min[ 1 ] 是到下标 1 结尾的最小子数组乘积： prefix_ min[ 1] = min(3, 2 3=6, 2 3=6) 不对，经典递推： i=0: (2,2) i=1: max(3, 2 3=6, 2 3=6)=6, min(3, 2 3=6, 2 3=6)=3? 错！ 重算： i=0: max=2, min=2 i=1: 候选(3, 2 3=6, 2 3=6) → max=6, min=3（因为3更小） 对。 所以 prefix_ min[ 1 ]=3 不是 -12。 我们发现之前的 suffix_ min 算错了。我们来正确计算。 正确计算 suffix_ min： i=4: suffix_ max[ 4]=-1, suffix_ min[ 4 ]=-1 i=3: 候选(4, 4×-1=-4, 4×-1=-4) → max=4, min=-4 i=2: 候选(-2, -2×4=-8, -2×-4=8) → max=8, min=-8 i=1: 候选(3, 3×8=24, 3×-8=-24) → max=24, min=-24 i=0: 候选(2, 2×24=48, 2×-24=-48) → max=48, min=-48 所以 suffix_ max = [ 48,24,8,4,-1], suffix_ min = [ -48,-24,-8,-4,-1 ] prefix_ max = [ 2,6,-2,4,-4], prefix_ min=[ 2,3,-12,-48,48 ]（这里我快速递推： i=0: (2,2) i=1: max(3,6,6)=6, min(3,6,6)=3 i=2: max(-2,6* -2=-12,3* -2=-6) = -2, min(-2,-12,-6)=-12 i=3: max(4,-2 4=-8,-12 4=-48)=4, min(4,-8,-48)=-48 i=4: max(-1,4* -1=-4,-48* -1=48)=48, min(-1,-4,48)=-4 所以 prefix_ min=[ 2,3,-12,-48,-4 ] 注意最后是 -4，不是 48 我写错了。修正： i=4: 候选(-1, 4* -1=-4, -48* -1=48) → max=48, min=-4 对，所以 prefix_ min[ 4 ] = -4。 现在枚举 p： p=0: max(2 24=48, 2 -24=-48) → 48 p=1: max(6 8=48, 3 -8=-24) → 48 p=2: max(-2 4=-8, -12 -4=48) → 48 p=3: max(4* -1=-4, -48* -1=48) → 48 所以多个 p 得到 48。但 48 可能吗？ p=2: prefix_ min[ 2] = -12 对应子数组 [ 2,3,-2] 乘积 -12，suffix_ min[ 3] = -4 对应子数组 [ 4,-1] 乘积 -4，相乘 (-12) (-4)=48。 这在翻转后对应什么？p=2 对应原数组分割 [ 0..2] 和 [ 3..4]，翻转区间是 [ p+1, r] 即 [ 3,4]，翻转后数组 [ 2,3,-2, -1,4]。最大子数组乘积是 3 -2* -1* 4=24，不是 48。 所以候选 48 并不对应实际的一个子数组，因为 prefix_ min[ 2] 和 suffix_ min[ 3 ] 对应的子数组在原数组中不相邻，翻转后也不能连成一段（因为中间隔了未翻转部分）。 这说明我们的枚举方法有缺陷。实际上，我们枚举 p 时，必须确保两段在原数组中相邻，翻转其中一段后它们才能连起来。我们的公式错误地允许了任意两段相乘。 步骤10：修正方法 正确方法：枚举翻转区间 [ l,r ]，然后计算新数组的最大子数组乘积，但这样 O(n³)。优化： 我们可以用 O(n²) 的时间枚举所有区间，对每个区间翻转，用类似最大子数组乘积的方法 O(n) 计算，总体 O(n³) 仍大。 但注意到，翻转区间 [ l,r ] 后，最大子数组要么完全在翻转区间内（同原数组），要么跨越边界。跨越边界时，一定是原数组中以 l-1 结尾的某段和以 r+1 开头的某段，加上整个翻转区间，因为翻转区间是整体反转，它的最大/最小乘积可以预处理。 定义： max_prod_from[i] = 从 i 开始的最大连续乘积（类似 suffix_ max 但必须从 i 开始） min_prod_from[i] max_prod_to[i] = 以 i 结尾的最大连续乘积（prefix_ max[ i ]） 然后翻转区间 [ l,r ] 后，新数组的最大子数组乘积候选为： 完全在左边：max_ prod_ to[ l-1 ] 完全在右边：max_ prod_ from[ r+1 ] 跨越左边和翻转区间：max{ max_ prod_ to[ l-1] * max_ prod_ rev, min_ prod_ to[ l-1] * min_ prod_ rev } 等，其中 max_ prod_ rev 是翻转区间的最大连续乘积（等于原区间从 r 到 l 的方向计算，可以用类似 suffix/prefix 的方法得到）。 跨越翻转区间和右边：类似。 这样，如果我们预处理出每个区间的正反方向最大最小乘积，就可以 O(1) 计算每个翻转区间的结果。但预处理所有区间是 O(n²)，加上枚举区间 O(n²)，总体 O(n²) 可行。 由于时间关系，我们给出最终 O(n²) 的算法步骤（适用于 n 不太大时）： 预处理原数组的 prefix_ max, prefix_ min, suffix_ max, suffix_ min。 预处理 rev_ max[ l][ r] 和 rev_ min[ l][ r] 表示原数组区间 [ l,r ] 反转后的最大/最小连续乘积（从右到左计算，等价于从 r 到 l 的正向计算，可以用类似 suffix 的方法在 O(n²) 内算出）。 初始答案 = 经典最大子数组乘积。 枚举所有可能的翻转区间 [ l,r]（0 <= l <= r < n）： 不跨越边界的情况已在经典答案中。 跨越左边和翻转区间：如果 l>0，计算候选 = 最优组合(prefix_ max[ l-1], prefix_ min[ l-1], rev_ max[ l][ r], rev_ min[ l][ r ])，即四种乘法的最大值。 跨越翻转区间和右边：如果 r<n-1，计算候选 = 最优组合(rev_ max[ l][ r], rev_ min[ l][ r], suffix_ max[ r+1], suffix_ min[ r+1 ])。 跨越左、翻转、右三部分：如果 l>0 且 r<n-1，候选 = 最优组合(prefix_ max[ l-1], prefix_ min[ l-1], rev_ max[ l][ r], rev_ min[ l][ r], suffix_ max[ r+1], suffix_ min[ r+1 ])，即八种乘法的最大值。 更新全局最大值。 这个算法是 O(n²)，在 n <= 200 时可行。对于更大 n，可能有 O(n) 的解法，但更复杂，需进一步推导。 总结 本题核心在于理解翻转操作如何改变连续乘积的拼接方式，并通过预处理各个方向的最大最小乘积，枚举翻转区间来求得可能的最大乘积。由于完整 O(n) 解法较复杂，这里给出了 O(n²) 的可行思路。你可以先实现 O(n²) 版本，再尝试优化。