最大子段和问题的变种：允许至多翻转一次子数组的最大子段和
字数 14681 2025-12-06 07:16:48

最大子段和问题的变种：允许至多翻转一次子数组的最大子段和

题目描述
给定一个整数数组 `nums``，你可以选择最多翻转一个连续子数组（将子数组中的元素顺序反转），之后，求这个数组的最大子段和（即连续子数组的最大和）。你需要返回翻转一次后能得到的最大子段和。

注意：

  • 你可以选择不翻转任何子数组。
  • 翻转操作最多执行一次，即翻转一个子数组后，不能再翻转其他部分。
  • 子数组至少包含一个元素。
  • 数组长度 n 满足 1 <= n <= 10^4，数组元素可能为负数、零或正数。

示例 1
输入：nums = [1, -2, 3, 4]
输出：8
解释：翻转子数组 [1, -2] 得到 [-2, 1, 3, 4]，最大子段和为 1+3+4=8（对应子数组 [1,3,4]）。不翻转时最大子段和是 3+4=7，所以最优是 8。

示例 2
输入：nums = [-1, -1]
输出：-1
解释：翻转任意子数组后数组不变，最大子段和是单个元素 -1。

解题过程

这个问题可以拆解为几个步骤。我们先从基础的最大子段和问题开始，逐步引入翻转操作。

1. 基础：最大子段和（Kadane算法）
对于数组 nums，定义 dp[i] 为以第 i 个元素结尾的最大子段和。状态转移方程为：
dp[i] = max(dp[i-1] + nums[i], nums[i])
最终答案是所有 dp[i] 的最大值。
我们可以在一次遍历中计算，用 cur 记录当前连续和，maxSum 记录全局最大和。
这是后续计算的基础。

2. 问题分析
翻转一个子数组 [l, r] 的效果是：将原数组分为三部分：A = nums[0..l-1]，B = nums[l..r]，C = nums[r+1..n-1]。
翻转 B 后，数组变为 A + reverse(B) + C。
我们需要在这个新数组中找最大子段和。
注意：最大子段和可能完全在 A 中，完全在 C 中，跨越 A 和 reverse(B)，跨越 reverse(B) 和 C，或完全在 reverse(B) 中。
直接枚举所有 l, r 是 O(n²)，会超时。需要更高效的方法。

3. 关键观察
翻转 B 后，B 内部元素的顺序反转了。但最大子段和是连续的一段，它可能包含 B 的一部分或全部。
实际上，翻转 B 后，如果有一段子数组跨越了 B 的边界，比如从 A 的末尾到 B 的开头（翻转后 B 的开头是原 B 的末尾），那相当于在原数组中，我们取了 A 的后缀和 B 的后缀（因为翻转后原 B 的后缀变成了新数组里 B 部分的前缀）。
更形式化地，我们考虑原数组的任意两个子数组 nums[i..j] 和 nums[k..l]，且 j < k，翻转它们之间的子数组 nums[j+1..k-1] 后，这两个子数组就会连在一起。
但这样还是太复杂。

另一种思路：
定义 prefixMax[i] 为原数组前 i 个元素（下标 0 到 i-1）的最大子段和。
定义 suffixMax[i] 为原数组后 n-i 个元素（下标 i 到 n-1）的最大子段和。
如果我们翻转子数组 [l, r]，那么新数组由三部分组成：A = nums[0..l-1]，reverse(B) = nums[r..l]，C = nums[r+1..n-1]。
考虑新数组中的最大子段和，它可能是：

  • 完全在 A 中：即 prefixMax[l]。
  • 完全在 C 中：即 suffixMax[r+1]。
  • 跨越 A 和 reverse(B)：即 A 的后缀最大和 + reverse(B) 的前缀最大和。但 reverse(B) 的前缀对应原数组 B 的后缀。
  • 跨越 reverse(B) 和 C：即 reverse(B) 的后缀最大和 + C 的前缀最大和。reverse(B) 的后缀对应原数组 B 的前缀。
  • 完全在 reverse(B) 中：即 B 内部翻转后的最大子段和，也就是原 B 的最大子段和（因为翻转不改变子段和，只是顺序变了，但子段和是元素和，与顺序无关，所以这部分其实就是原 B 的最大子段和）。

4. 重新表述
设原数组为 a。
定义：

  • leftMax[i]：原数组前 i 个元素（下标 0 到 i-1）的最大子段和。
  • rightMax[i]：原数组后 n-i 个元素（下标 i 到 n-1）的最大子段和。
  • leftSum[i]：以 i-1 结尾的最大后缀和（即从某个位置到 i-1 的最大和）。
  • rightSum[i]：以 i 开头的最大前缀和（即从 i 到某个位置的最大和）。

翻转区间 [l, r] 后，新数组的最大子段和可能是以下四种情况的最大值：

  1. 不跨越翻转区间：leftMax[l] 或 rightMax[r+1]。
  2. 跨越左边和翻转区间：leftSum[l] + (a[r] + a[r-1] + ... + a[x]) 的最大值，其中 x 在 [l, r] 且是原数组从 r 往左的后缀和最大的一段。但更直接地，我们可以计算原数组在区间 [l, r] 的最大后缀和，记作 suffixIn[l..r]，那么跨越左边的和就是 leftSum[l] + suffixIn[l..r]。
  3. 跨越翻转区间和右边：原数组在区间 [l, r] 的最大前缀和 prefixIn[l..r] + rightSum[r+1]。
  4. 跨越左边、整个翻转区间、右边：leftSum[l] + sum(l..r) + rightSum[r+1]。

但这样需要为每个区间 [l, r] 计算内部的最大前缀和、最大后缀和，仍是 O(n²)。

5. 高效算法
我们换个角度：
翻转区间 [l, r] 后，新数组里会有一段子数组由“原数组的一个后缀（在 l 之前） + 原数组的一个子数组（在 [l, r] 内但顺序反转） + 原数组的一个前缀（在 r 之后）”组成。但顺序反转后，原数组 [l, r] 内的子段在新数组里是连续但反序的。
实际上，如果我们定义：

  • L[i]：以 i 结尾的最大子段和（就是普通的最大子段和）。
  • R[i]：以 i 开头的最大子段和。

那么翻转 [l, r] 后，我们可以得到一种新的子段：原数组从某个位置 j（j ≤ l）到 l-1 的后缀最大和 + 原数组从 r 到某个位置 k（k ≥ l）的后缀最大和（但这里注意顺序，翻转后，原数组的 [l, r] 段反序，所以在新数组中，从左边跨到翻转段的部分，对应原数组左边的一段后缀和原数组 [l, r] 内的一段后缀（因为翻转后原后缀变前缀）。
更形式化地，考虑翻转区间 [l, r]，新数组中可能有一段子数组由“原数组的 [x, l-1] 和原数组的 [y, r] 组成，且 l ≤ y ≤ r”，但翻转后这两段是连续的，且原数组的 [y, r] 段在新数组中是反序的，但求和我们只关心和，顺序不影响和。
所以我们可以定义：

  • leftGain[i]：原数组在 i 左侧（不含 i）能得到的最大后缀和（即以 i-1 结尾的最大后缀和）。
  • rightGain[i]：原数组在 i 右侧（含 i）能得到的最大前缀和（即以 i 开头的最大前缀和）。

但这样还是需要枚举区间。

6. 最终转换
注意到，翻转区间 [l, r] 后，新数组的最大子段和可以表示为：
max( leftMax[l], rightMax[r+1], leftGain[l] + rightGain[r] ) 吗？ 不对，因为 leftGain[l] 是原数组在 l 左侧的最大后缀和，rightGain[r] 是原数组在 r 右侧的最大前缀和，但中间翻转的部分是原数组的 [l, r] 段，它的和是 sum(l, r)。
实际上，如果我们取原数组的一个后缀（在 l 左边）和原数组的一个前缀（在 r 右边），中间夹着翻转的整个 [l, r]，那么新数组中的子段和就是 leftGain[l] + sum(l, r) + rightGain[r+1]。
但最大子段和不一定包含整个翻转区间。它可以只包含翻转区间的一部分。
然而，我们可以证明：对于翻转区间 [l, r]，新数组的最大子段和等于：
max( leftMax[l], rightMax[r+1], leftGain[l] + maxSubarraySumReverse(l, r) + rightGain[r+1] )，其中 maxSubarraySumReverse(l, r) 是原数组 [l, r] 段翻转后的最大子段和，由于翻转不改变子段和（只是顺序），所以它等于原数组 [l, r] 段的最大子段和。
但这样 leftGain 和 rightGain 中间夹的是翻转区间的最大子段和，而不是整个区间和。
其实，我们可以考虑新数组中的子段由三部分组成：左边一段（原数组 l 左侧的后缀）、中间一段（原数组 [l, r] 内的子数组，但顺序反转）、右边一段（原数组 r 右侧的前缀）。
这三段在新数组中连续。
设左边一段的和为 L，中间一段在原数组对应子段为 [x, y]（l ≤ x ≤ y ≤ r），右边一段的和为 R。
那么新数组的子段和为 L + sum(x, y) + R。
其中 L 是原数组中以 l-1 结尾的某段后缀（可能为空），R 是原数组中以 r+1 开头的某段前缀（可能为空）。
那么对于固定的 l, r，我们需要最大化 L + sum(x, y) + R，其中 L 是左后缀最大和（记作 leftSuffix[l]），R 是右前缀最大和（记作 rightPrefix[r]），sum(x, y) 是原数组 [l, r] 内的最大子段和。
所以翻转 [l, r] 能得到的最大子段和是：
max( leftMax[l], rightMax[r+1], leftSuffix[l] + maxSubarray(l, r) + rightPrefix[r+1] )。
其中 leftMax[l] 和 rightMax[r+1] 对应不跨越翻转区间的情况。
但注意，leftSuffix[l] 可能为 0（表示左边不取），同样 rightPrefix[r+1] 可能为 0。
而 maxSubarray(l, r) 是原数组 [l, r] 段的最大子段和（可以用 Kadane 在区间上计算，但需要 O(n²)）。

7. 优化
我们枚举翻转区间的左端点 l，然后从 l 到 n-1 枚举右端点 r，同时维护 [l, r] 段的最大子段和。
定义 midMax 为当前区间 [l, r] 的最大子段和。当我们固定 l，逐步增大 r 时，可以用 Kadane 算法更新 midMax。
同时，我们已知 leftSuffix[l] 是固定的（原数组在 l 左侧的最大后缀和，可以为 0）。
rightPrefix[r+1] 可以预处理：rightPrefix[i] 表示原数组从 i 开始的最大前缀和（至少包含一个元素）。
那么对于当前 l, r，翻转 [l, r] 能得到的最大子段和候选值为：
leftSuffix[l] + midMax + rightPrefix[r+1]。
另外，还有不跨越翻转区间的情况：leftMax[l] 和 rightMax[r+1]。
我们在所有 l, r 上取最大值即可。

8. 预处理数组

  • leftMax[i]：前 i 个元素的最大子段和。leftMax[0]=-inf，然后从左到右用 Kadane 更新。
  • rightMax[i]：后 n-i 个元素的最大子段和。rightMax[n]=-inf，从右到左用 Kadane 更新。
  • leftSuffix[i]：以 i-1 结尾的最大后缀和（可以为 0，表示左边不取）。leftSuffix[0]=0，leftSuffix[i] = max(0, leftSuffix[i-1] + nums[i-1])。
  • rightPrefix[i]：以 i 开头的最大前缀和（至少一个元素）。rightPrefix[n]=-inf，从右向左计算：rightPrefix[i] = max(nums[i], nums[i] + rightPrefix[i+1])，但注意至少取一个元素，所以不能为 0。不过在我们的跨越三部分公式中，右边一段可以没有，所以我们可以定义 rightPrefix[i] 为从 i 开始的最大前缀和（允许为空，和为 0）。但为了统一，我们允许右边为空，即 rightPrefix[n]=0，rightPrefix[i] = max(0, nums[i] + rightPrefix[i+1])？不对，如果右边全是负数，我们应该不取，即为 0。所以定义 rightPrefix[i] 为从 i 开始的最大前缀和（非空），但我们可以用类似 leftSuffix 的方式，定义 rightGain[i] 为从 i 开始的最大前缀和（允许为空，即 0）。但公式中是 rightPrefix[r+1]，它可能为 0。
    我们定义 rightGain[i] 为原数组从 i 到末尾的最大前缀和（允许为空，和为 0）。
    rightGain[n]=0，rightGain[i] = max(0, nums[i] + rightGain[i+1])。
    注意：这样如果右边一段全负，就不取，和为 0。

9. 算法步骤

  1. 预处理：
    • leftMax[i]：前 i 个元素的最大子段和。
    • rightMax[i]：后 n-i 个元素的最大子段和。
    • leftSuffix[i]：以 i-1 结尾的最大后缀和（非负，因为可以不取左边）。
    • rightGain[i]：从 i 开始的最大前缀和（非负）。
  2. 初始化答案 ans 为不翻转的最大子段和（即 leftMax[n]）。
  3. 枚举左端点 l：
    • 初始化 cur=0, midMax=0（因为 [l, l-1] 区间为空）。
    • 从 l 到 n-1 枚举右端点 r：
      • 用 Kadane 更新 cur = max(cur + nums[r], nums[r])，midMax = max(midMax, cur)。
      • 计算翻转 [l, r] 的候选值：candidate = leftSuffix[l] + midMax + rightGain[r+1]。
      • 同时考虑不跨越的情况：candidate = max(candidate, leftMax[l], rightMax[r+1])。
      • 更新 ans = max(ans, candidate)。
  4. 返回 ans。

10. 边界处理

  • 当 l=0 时，leftSuffix[0]=0，左边为空。
  • 当 r=n-1 时，rightGain[n]=0，右边为空。
  • 注意 rightMax[r+1] 当 r+1=n 时，表示右边为空，最大子段和为负无穷（但右边为空时，我们不考虑右边单独一段，因为这种情况已经被 leftMax[l] 覆盖了）。但为了统一，我们定义 rightMax[n] = -inf（用很负数代替），这样在比较时，如果右边全负，rightMax[n] 会是负数，但 leftSuffix[l] + midMax + rightGain[r+1] 可能更大。

11. 示例验证
以 nums = [1, -2, 3, 4] 为例：

  • 预处理：

    • leftSuffix = [0, 1, 0, 3, 7]（长度为5，leftSuffix[0]=0, leftSuffix[1]=max(0,0+1)=1, leftSuffix[2]=max(0,1+(-2))=0, leftSuffix[3]=max(0,0+3)=3, leftSuffix[4]=max(0,3+4)=7）。

    • rightGain = [7, 7, 7, 4, 0]（从右到左：rightGain[4]=0, rightGain[3]=max(0,4+0)=4, rightGain[2]=max(0,3+4)=7, rightGain[1]=max(0,-2+7)=5? 等等，我们重新算：
      从右到左，rightGain[i] = max(0, nums[i] + rightGain[i+1])。
      rightGain[4]=0,
      i=3: rightGain[3]=max(0,4+0)=4,
      i=2: rightGain[2]=max(0,3+4)=7,
      i=1: rightGain[1]=max(0,-2+7)=5,
      i=0: rightGain[0]=max(0,1+5)=6。
      但注意，rightGain[i] 是从 i 开始的最大前缀和（非负），所以应该是允许从 i 开始取一段连续子数组，和最大且非负。但这样计算实际上是允许任意长度（包括0），所以是最大前缀和（非负）。但我们的公式中，rightGain[r+1] 是右边一段的最大和（非负），所以应该是从 r+1 开始的最大子段和（非负）。所以我们用 rightGain[i] 表示从 i 开始的最大子段和（非负）。但最大子段和不一定从 i 开始，可能从后面开始。所以我们需要的是从 i 开始的最大前缀和（非负），而不是最大子段和。
      重新定义：rightPrefixMax[i] 为从 i 开始的最大前缀和（非负）。
      rightPrefixMax[4]=0,
      i=3: max(0,4)=4,
      i=2: max(0,3, 3+4)=7, 等等，前缀和必须从 i 开始连续，所以应该是 rightStartMax[i] = max(0, nums[i], nums[i]+nums[i+1], ...) 的最大值，但可以递推：rightStartMax[i] = max(0, nums[i] + rightStartMax[i+1])。
      因为如果从 i 开始取一段，要么不取（0），要么取 nums[i] 以及后面的一段（但必须连续从 i 开始）。所以递推式正确。
      我们重新计算：
      rightStartMax[4]=0,
      i=3: max(0, 4+0)=4,
      i=2: max(0, 3+4)=7,
      i=1: max(0, -2+7)=5,
      i=0: max(0, 1+5)=6。
      但注意，从 i=1 开始，取 [-2,3,4] 和是5，没错。

      但我们的公式中，右边一段是原数组从 r+1 开始的一段前缀（在新数组中连续），所以应该是从 r+1 开始的最大前缀和（非负），所以用 rightStartMax 是对的。
      但注意，我们之前公式中写的是 rightGain[r+1]，就是 rightStartMax[r+1]。

  • 枚举 l=0:

    • cur=0, midMax=0
    • r=0: cur=max(0+1,1)=1, midMax=1, candidate = leftSuffix[0]+midMax+rightStartMax[1] = 0+1+5=6, 同时与 leftMax[0]（前0个最大子段和，设为 -inf）和 rightMax[1]（后3个最大子段和，即7）比较，取 max(6,7)=7，ans=7。
    • r=1: cur=max(1+(-2),-2)=-1, midMax=1（不变），candidate=0+1+rightStartMax[2]=1+7=8, 与 leftMax[0] 和 rightMax[2]（后2个最大子段和，即7）比较，max(8,7)=8，ans=8。
    • r=2: cur=max(-1+3,3)=3, midMax=max(1,3)=3, candidate=0+3+rightStartMax[3]=3+4=7, max(7,7)=7，ans=8。
    • r=3: cur=3+4=7, midMax=7, candidate=0+7+rightStartMax[4]=7+0=7, max(7,rightMax[4]（后0个为 -inf）)=7，ans=8。

  • 枚举 l=1,2,3 等，都不会超过8。
    最终 ans=8，正确。

12. 时间复杂度
预处理 O(n)，枚举 l 和 r 是 O(n²)，在 n≤10^4 时可能超时。但我们可以优化：
注意到固定 l，我们只需要一次遍历 r 并维护 midMax（区间 [l, r] 的最大子段和），这是 O(n) 的，所以总 O(n²)。
n=10^4 时，O(n²) 是 10^8，可能勉强过（在优化良好的情况下），但通常希望 O(n)。
有没有 O(n) 方法？
我们可以考虑不枚举区间，而是计算“翻转一次”带来的最大增益。
但本题通常的 O(n) 解法是：
定义 f[i] 为以 i 结尾的最大子段和（不翻转）。
定义 g[i] 为以 i 开头的最大子段和（不翻转）。
定义 h[i] 为在 i 处翻转（即翻转的区间以 i 为左端点或右端点）能得到的最大增益。
但更简单的 O(n) 解法是：
计算不翻转时的最大子段和 maxSum。
然后计算翻转一个子数组能增加的最大值。
翻转一个子数组 [l, r] 相当于，我们找到两个不相交的子数组：一个在左边（以 l-1 结尾），一个在右边（以 r+1 开头），中间夹着原数组的 [l, r] 段，但顺序反转。但顺序反转不影响和，所以中间段的和就是原数组 [l, r] 的和。
那么新数组中的子段和就是：左边后缀和 + 中间段和 + 右边前缀和。
我们希望最大化这个值。
我们可以枚举中间段的两个端点，但可以转换成：
对于每个位置 i，计算以 i 结尾的最大后缀和 leftSuffix[i]，和以 i 开头的最大前缀和 rightPrefix[i]。
然后，问题变成找两个位置 l <= r，使得 leftSuffix[l] + (sum(l, r)) + rightPrefix[r+1] 最大。
令 total = leftSuffix[l] + rightPrefix[r+1] + sum(l, r)。
我们可以固定 r，求最大的 leftSuffix[l] + sum(l, r)，其中 l ≤ r。
定义 bestLeft[r] = max_{0<=l<=r} (leftSuffix[l] + sum(l, r))。
而 sum(l, r) = prefixSum[r+1] - prefixSum[l]，其中 prefixSum[i] 是前 i 个元素的和。
所以 leftSuffix[l] + sum(l, r) = leftSuffix[l] - prefixSum[l] + prefixSum[r+1]。
对于固定的 r，prefixSum[r+1] 是常数，所以我们只需要最大化 leftSuffix[l] - prefixSum[l]，记作 val[l]。
那么 bestLeft[r] = prefixSum[r+1] + max_{0<=l<=r} val[l]。
我们可以从左到右扫描，维护 maxVal = max(val[l])。
然后对于每个 r，候选值为 bestLeft[r] + rightPrefix[r+1]。
但注意，leftSuffix[l] 是以 l-1 结尾的最大后缀和，所以 leftSuffix[0]=0，leftSuffix[l] = max(0, leftSuffix[l-1] + nums[l-1])。
val[l] = leftSuffix[l] - prefixSum[l]。
然后 bestLeft[r] = prefixSum[r+1] + max_{0<=l<=r} val[l]。
那么翻转区间 [l, r] 对应的新子段和为 bestLeft[r] + rightPrefix[r+1]。
但这样我们假定了子段包含整个翻转区间 [l, r]。
如果子段只包含翻转区间的一部分，会怎样？
实际上，我们之前已经分析过，新数组的最大子段和可能是三部分：左边后缀、中间一段（原数组 [l, r] 的子段）、右边前缀。
如果我们设中间一段是原数组的 [x, y]（l ≤ x ≤ y ≤ r），那么新子段和为 leftSuffix[l] + sum(x, y) + rightPrefix[r+1]。
为了最大化，我们会选择 [x, y] 为 [l, r] 内的最大子段和。
所以我们需要的是 leftSuffix[l] + maxSubarray(l, r) + rightPrefix[r+1]。
但这样又回到了需要区间最大子段和的问题。
然而，我们可以考虑另一种思路：
翻转区间 [l, r] 后，新数组的最大子段和等价于：
max( leftMax[l], rightMax[r+1], leftSuffix[l] + maxSubarray(l, r) + rightPrefix[r+1] )。
其中 maxSubarray(l, r) 是区间 [l, r] 的最大子段和。
我们可以枚举 l，然后随着 r 增大，用 Kadane 维护 maxSubarray(l, r)。
这就是我们之前的 O(n²) 算法。
对于 n=10^4，O(n²) 可能过不了。但我们可以尝试优化常数，或者寻求 O(n) 解法。

13. 最终采用的 O(n) 解法
实际上，这个问题可以转化为：
不翻转的最大子段和记为 ans。
翻转一次相当于，我们可以选择两个不相交的子数组，然后拼接起来（因为翻转中间段相当于把中间段反转，但拼接时中间段和不变，所以可以看作两个子数组中间夹着一个反转段，但反转段本身可以是一个子数组）。
更准确地说，翻转区间 [l, r] 后，新数组中的一个子段可以看作由三部分组成：原数组的一个后缀（在 l 之前）、原数组的一个子数组（在 [l, r] 内）、原数组的一个前缀（在 r 之后）。
我们想要最大化这三段的和。
定义 leftBest[i] 为原数组前 i 个元素中，两段不相交子数组的最大和，其中一段以 i-1 结尾，另一段在其左边。
但这样太复杂。
其实有一个巧妙的 O(n) 解法：
翻转一个子数组等价于，我们可以选择两个不相交的子数组，然后让它们的顺序交换（即先取右边的，再取左边的）。
但翻转是反转一个连续段，所以新子段可以是：原数组的一个子数组，或者两段不相交的子数组的和（但顺序是右边的先，左边的后）。
所以问题转化为：求原数组的两个不相交子数组的最大和，但顺序可以交换（即我们可以先取后面一段，再取前面一段）。
因为翻转一个区间，相当于把后面一段放到前面，前面一段放到后面，中间的反转段相当于一个子数组。
但注意，如果只取两段，中间的反转段可能为空，即我们只是交换了两段的位置。
所以翻转一次能得到的最大子段和，等于以下两种情况的最大值：

  1. 原数组的最大子段和（不翻转）。
  2. 原数组的两段不相交子数组的最大和，但考虑顺序（即可以后一段在前，前一段在后）。
    因为如果我们取两段不相交子数组，我们可以通过翻转它们之间的部分来使它们相邻。
    具体地，设两段子数组的起始和结束位置为 [l1, r1] 和 [l2, r2]，且 r1 < l2。
    翻转区间 [r1+1, l2-1]，则新数组中这两段就相邻了，且顺序变为先 [l2, r2] 后 [l1, r1]。
    所以新子段和为两段和相加。
    因此，问题等价于求原数组的两段不相交子数组的最大和。
    这是一个经典问题：最大两段子段和。
    但注意，两段子数组的顺序可以交换，所以我们求的是“两段不相交子数组的最大和”，不考虑顺序。
    求法：
    从左到右求 left[i] 表示前 i 个元素的最大子段和。
    从右到左求 right[i] 表示后 n-i 个元素的最大子段和。
    然后枚举分割点 i，left[i] + right[i] 的最大值就是两段不相交子数组的最大和。
    但这样两段顺序是左前右后。
    如果交换顺序，即右前左后，那么相当于求 left[i] 和 right[i] 但方向相反。
    但两段不相交子数组的最大和，与顺序无关，因为两段的和是加法交换的。
    所以直接求 max_{i} (left[i] + right[i]) 即可。
    但注意，两段可能有一段为空，这时就是一段子数组的情况。
    所以翻转一次的最大子段和 = max(一段的最大子段和, 两段不相交子数组的最大和)。
    但这样对吗？我们检查示例1：
    原数组 [1, -2, 3, 4]，一段最大子段和是7（[3,4]）。
    两段不相交子数组最大和：可以取 [1] 和 [3,4]，和为8。
    所以答案是8，正确。
    示例2：[-1, -1]，一段最大子段和是-1，两段最大和是-2（取两个-1），所以最大是-1，正确。
    再测试一个数组 [1,2,3,-4,5]，一段最大是6（[1,2,3]），两段可以取 [1,2,3] 和 [5]，和是6+5=11，翻转区间 [3,3]（即-4）使得 [1,2,3] 和 [5] 相邻，新数组为 [1,2,3,5,-4]，最大子段和为11，正确。
    所以这个转换是正确的。

14. 算法总结

  1. 求原数组的最大子段和 singleMax（用 Kadane）。
  2. 求两段不相交子数组的最大和 doubleMax：
    • 从左到右计算 left[i]：前 i 个元素的最大子段和（left[0]=-inf，用 Kadane 更新）。
    • 从右到左计算 right[i]：后 n-i 个元素的最大子段和（right[n]=-inf，用 Kadane 更新）。
    • 遍历每个分割点 i（0<=i<=n），doubleMax = max(doubleMax, left[i] + right[i])。
  3. 答案 = max(singleMax, doubleMax)。

注意：left[i] 是前 i 个元素的最大子段和（子段不一定以 i-1 结尾），right[i] 是后 n-i 个元素的最大子段和。
这样，left[i] + right[i] 表示两段不相交子数组的和，一段在前 i 个元素中，一段在后 n-i 个元素中。
但两段可能有一段为空，所以 doubleMax 至少是 singleMax。
所以答案就是 doubleMax。
但注意，如果全为负数，doubleMax 可能是两个负数相加，小于 singleMax（最大单个元素），但 left[i] 和 right[i] 在计算时，Kadane 算法会处理全负数情况，left[i] 是前 i 个元素的最大子段和（至少一个元素），所以 doubleMax 可能小于 singleMax，取 max 即可。

15. 时间复杂度
O(n)，空间 O(n)（可以优化到 O(1)）。

16. 最终算法步骤

  1. 初始化 singleMax 为 Kadane 算法求整个数组的最大子段和。
  2. 计算 left 数组：left[0] = -inf，cur=0, maxSoFar=-inf，遍历 i 从 0 到 n-1：
    cur = max(cur + nums[i], nums[i])，maxSoFar = max(maxSoFar, cur)，left[i+1] = maxSoFar。
  3. 计算 right 数组：right[n] = -inf，cur=0, maxSoFar=-inf，遍历 i 从 n-1 到 0：
    cur = max(cur + nums[i], nums[i])，maxSoFar = max(maxSoFar, cur)，right[i] = maxSoFar。
  4. 初始化 doubleMax = -inf，遍历 i 从 0 到 n：
    doubleMax = max(doubleMax, left[i] + right[i])。
  5. 返回 max(singleMax, doubleMax)。

17. 示例验证
nums = [1, -2, 3, 4]

  • singleMax: Kadane 得到 7（3+4）。
  • left: [ -inf, 1, 1, 3, 7 ]
  • right: 从右到左：
    初始化 cur=0, maxSoFar=-inf
    i=3: cur=4, maxSoFar=4, right[3]=4
    i=2: cur=max(4+3,3)=7, maxSoFar=7, right[2]=7
    i=1: cur=max(7+(-2),-2)=5, maxSoFar=7, right[1]=7
    i=0: cur=max(5+1,1)=6, maxSoFar=7, right[0]=7
    所以 right = [7,7,7,4,-inf]（right[4]未定义，但用 -inf）
  • 遍历 i:
    i=0: left[0]+right[0] = -inf+7 = -inf
    i=1: 1+7=8
    i=2: 1+7=8
    i=3: 3+4=7
    i=4: 7+(-inf) = -inf
    doubleMax=8
  • 答案 max(7,8)=8，正确。

18. 边界情况
全负数：[-1, -2]，singleMax=-1，left=[-inf, -1, -1]，right=[-1, -2, -inf]，doubleMax=max(-inf, -1-2=-3, -1+(-inf)=-inf) = -3，答案 max(-1,-3)=-1，正确。
单个元素：[5]，singleMax=5，left=[-inf,5]，right=[5,-inf]，doubleMax=5+(-inf)=-inf，答案5，正确。

19. 总结
本题的关键是将“翻转一个子数组”转化为“求两段不相交子数组的最大和”，因为翻转后，我们可以将两段原本不相交的子数组通过翻转中间部分而相邻，从而合并成一段。
因此，问题简化为求原数组的两段不相交子数组的最大和，这可以用前后缀分解在线性时间内解决。

这样，我们就得到了一个 O(n) 时间、O(n) 空间的优美解法。

最大子段和问题的变种：允许至多翻转一次子数组的最大子段和 题目描述 给定一个整数数组 `nums `` ，你可以选择最多翻转一个连续子数组（将子数组中的元素顺序反转），之后，求这个数组的最大子段和（即连续子数组的最大和）。你需要返回翻转一次后能得到的最大子段和。 注意： 你可以选择不翻转任何子数组。 翻转操作最多执行一次，即翻转一个子数组后，不能再翻转其他部分。 子数组至少包含一个元素。 数组长度 n 满足 1 <= n <= 10^4 ，数组元素可能为负数、零或正数。 示例 1 输入： nums = [1, -2, 3, 4] 输出： 8 解释：翻转子数组 [1, -2] 得到 [-2, 1, 3, 4] ，最大子段和为 1+3+4=8 （对应子数组 [1,3,4] ）。不翻转时最大子段和是 3+4=7 ，所以最优是 8 。 示例 2 输入： nums = [-1, -1] 输出： -1 解释：翻转任意子数组后数组不变，最大子段和是单个元素 -1 。 解题过程 这个问题可以拆解为几个步骤。我们先从基础的最大子段和问题开始，逐步引入翻转操作。 1. 基础：最大子段和（Kadane算法） 对于数组 nums ，定义 dp[i] 为以第 i 个元素结尾的最大子段和。状态转移方程为： dp[i] = max(dp[i-1] + nums[i], nums[i]) 最终答案是所有 dp[i] 的最大值。 我们可以在一次遍历中计算，用 cur 记录当前连续和， maxSum 记录全局最大和。 这是后续计算的基础。 2. 问题分析 翻转一个子数组 [l, r] 的效果是：将原数组分为三部分： A = nums[0..l-1] ， B = nums[l..r] ， C = nums[r+1..n-1] 。 翻转 B 后，数组变为 A + reverse(B) + C 。 我们需要在这个新数组中找最大子段和。 注意：最大子段和可能完全在 A 中，完全在 C 中，跨越 A 和 reverse(B) ，跨越 reverse(B) 和 C ，或完全在 reverse(B) 中。 直接枚举所有 l, r 是 O(n²)，会超时。需要更高效的方法。 3. 关键观察 翻转 B 后， B 内部元素的顺序反转了。但最大子段和是连续的一段，它可能包含 B 的一部分或全部。 实际上，翻转 B 后，如果有一段子数组跨越了 B 的边界，比如从 A 的末尾到 B 的开头（翻转后 B 的开头是原 B 的末尾），那相当于在原数组中，我们取了 A 的后缀和 B 的后缀（因为翻转后原 B 的后缀变成了新数组里 B 部分的前缀）。 更形式化地，我们考虑原数组的任意两个子数组 nums[i..j] 和 nums[k..l] ，且 j < k ，翻转它们之间的子数组 nums[j+1..k-1] 后，这两个子数组就会连在一起。 但这样还是太复杂。 另一种思路： 定义 prefixMax[i] 为原数组前 i 个元素（下标 0 到 i-1）的最大子段和。 定义 suffixMax[i] 为原数组后 n-i 个元素（下标 i 到 n-1）的最大子段和。 如果我们翻转子数组 [l, r] ，那么新数组由三部分组成： A = nums[0..l-1] ， reverse(B) = nums[r..l] ， C = nums[r+1..n-1] 。 考虑新数组中的最大子段和，它可能是： 完全在 A 中：即 prefixMax[l] 。 完全在 C 中：即 suffixMax[r+1] 。 跨越 A 和 reverse(B) ：即 A 的后缀最大和 + reverse(B) 的前缀最大和。但 reverse(B) 的前缀对应原数组 B 的后缀。 跨越 reverse(B) 和 C ：即 reverse(B) 的后缀最大和 + C 的前缀最大和。 reverse(B) 的后缀对应原数组 B 的前缀。 完全在 reverse(B) 中：即 B 内部翻转后的最大子段和，也就是原 B 的最大子段和（因为翻转不改变子段和，只是顺序变了，但子段和是元素和，与顺序无关，所以这部分其实就是原 B 的最大子段和）。 4. 重新表述 设原数组为 a 。 定义： leftMax[i] ：原数组前 i 个元素（下标 0 到 i-1）的最大子段和。 rightMax[i] ：原数组后 n-i 个元素（下标 i 到 n-1）的最大子段和。 leftSum[i] ：以 i-1 结尾的最大后缀和（即从某个位置到 i-1 的最大和）。 rightSum[i] ：以 i 开头的最大前缀和（即从 i 到某个位置的最大和）。 翻转区间 [l, r] 后，新数组的最大子段和可能是以下四种情况的最大值： 不跨越翻转区间： leftMax[l] 或 rightMax[r+1] 。 跨越左边和翻转区间： leftSum[l] + (a[r] + a[r-1] + ... + a[x]) 的最大值，其中 x 在 [l, r] 且是原数组从 r 往左的后缀和最大的一段。但更直接地，我们可以计算原数组在区间 [l, r] 的最大后缀和，记作 suffixIn[l..r] ，那么跨越左边的和就是 leftSum[l] + suffixIn[l..r] 。 跨越翻转区间和右边：原数组在区间 [l, r] 的最大前缀和 prefixIn[l..r] + rightSum[r+1] 。 跨越左边、整个翻转区间、右边： leftSum[l] + sum(l..r) + rightSum[r+1] 。 但这样需要为每个区间 [l, r] 计算内部的最大前缀和、最大后缀和，仍是 O(n²)。 5. 高效算法 我们换个角度： 翻转区间 [l, r] 后，新数组里会有一段子数组由“原数组的一个后缀（在 l 之前） + 原数组的一个子数组（在 [l, r] 内但顺序反转） + 原数组的一个前缀（在 r 之后）”组成。但顺序反转后，原数组 [l, r] 内的子段在新数组里是连续但反序的。 实际上，如果我们定义： L[i] ：以 i 结尾的最大子段和（就是普通的最大子段和）。 R[i] ：以 i 开头的最大子段和。 那么翻转 [l, r] 后，我们可以得到一种新的子段：原数组从某个位置 j （j ≤ l）到 l-1 的后缀最大和 + 原数组从 r 到某个位置 k （k ≥ l）的后缀最大和（但这里注意顺序，翻转后，原数组的 [l, r] 段反序，所以在新数组中，从左边跨到翻转段的部分，对应原数组左边的一段后缀和原数组 [l, r] 内的一段后缀（因为翻转后原后缀变前缀）。 更形式化地，考虑翻转区间 [l, r] ，新数组中可能有一段子数组由“原数组的 [x, l-1] 和原数组的 [y, r] 组成，且 l ≤ y ≤ r”，但翻转后这两段是连续的，且原数组的 [y, r] 段在新数组中是反序的，但求和我们只关心和，顺序不影响和。 所以我们可以定义： leftGain[i] ：原数组在 i 左侧（不含 i）能得到的最大后缀和（即以 i-1 结尾的最大后缀和）。 rightGain[i] ：原数组在 i 右侧（含 i）能得到的最大前缀和（即以 i 开头的最大前缀和）。 但这样还是需要枚举区间。 6. 最终转换 注意到，翻转区间 [l, r] 后，新数组的最大子段和可以表示为： max( leftMax[l], rightMax[r+1], leftGain[l] + rightGain[r] ) 吗？ 不对，因为 leftGain[ l] 是原数组在 l 左侧的最大后缀和，rightGain[ r] 是原数组在 r 右侧的最大前缀和，但中间翻转的部分是原数组的 [l, r] 段，它的和是 sum(l, r) 。 实际上，如果我们取原数组的一个后缀（在 l 左边）和原数组的一个前缀（在 r 右边），中间夹着翻转的整个 [l, r] ，那么新数组中的子段和就是 leftGain[l] + sum(l, r) + rightGain[r+1] 。 但最大子段和不一定包含整个翻转区间。它可以只包含翻转区间的一部分。 然而，我们可以证明：对于翻转区间 [l, r] ，新数组的最大子段和等于： max( leftMax[l], rightMax[r+1], leftGain[l] + maxSubarraySumReverse(l, r) + rightGain[r+1] ) ，其中 maxSubarraySumReverse(l, r) 是原数组 [l, r] 段翻转后的最大子段和，由于翻转不改变子段和（只是顺序），所以它等于原数组 [l, r] 段的最大子段和。 但这样 leftGain 和 rightGain 中间夹的是翻转区间的最大子段和，而不是整个区间和。 其实，我们可以考虑新数组中的子段由三部分组成：左边一段（原数组 l 左侧的后缀）、中间一段（原数组 [l, r] 内的子数组，但顺序反转）、右边一段（原数组 r 右侧的前缀）。 这三段在新数组中连续。 设左边一段的和为 L ，中间一段在原数组对应子段为 [x, y] （l ≤ x ≤ y ≤ r），右边一段的和为 R 。 那么新数组的子段和为 L + sum(x, y) + R 。 其中 L 是原数组中以 l-1 结尾的某段后缀（可能为空）， R 是原数组中以 r+1 开头的某段前缀（可能为空）。 那么对于固定的 l, r ，我们需要最大化 L + sum(x, y) + R ，其中 L 是左后缀最大和（记作 leftSuffix[l] ）， R 是右前缀最大和（记作 rightPrefix[r] ）， sum(x, y) 是原数组 [l, r] 内的最大子段和。 所以翻转 [l, r] 能得到的最大子段和是： max( leftMax[l], rightMax[r+1], leftSuffix[l] + maxSubarray(l, r) + rightPrefix[r+1] ) 。 其中 leftMax[l] 和 rightMax[r+1] 对应不跨越翻转区间的情况。 但注意， leftSuffix[l] 可能为 0（表示左边不取），同样 rightPrefix[r+1] 可能为 0。 而 maxSubarray(l, r) 是原数组 [l, r] 段的最大子段和（可以用 Kadane 在区间上计算，但需要 O(n²)）。 7. 优化 我们枚举翻转区间的左端点 l ，然后从 l 到 n-1 枚举右端点 r ，同时维护 [l, r] 段的最大子段和。 定义 midMax 为当前区间 [l, r] 的最大子段和。当我们固定 l ，逐步增大 r 时，可以用 Kadane 算法更新 midMax 。 同时，我们已知 leftSuffix[l] 是固定的（原数组在 l 左侧的最大后缀和，可以为 0）。 rightPrefix[r+1] 可以预处理： rightPrefix[i] 表示原数组从 i 开始的最大前缀和（至少包含一个元素）。 那么对于当前 l, r ，翻转 [l, r] 能得到的最大子段和候选值为： leftSuffix[l] + midMax + rightPrefix[r+1] 。 另外，还有不跨越翻转区间的情况： leftMax[l] 和 rightMax[r+1] 。 我们在所有 l, r 上取最大值即可。 8. 预处理数组 leftMax[i] ：前 i 个元素的最大子段和。 leftMax[0]=-inf ，然后从左到右用 Kadane 更新。 rightMax[i] ：后 n-i 个元素的最大子段和。 rightMax[n]=-inf ，从右到左用 Kadane 更新。 leftSuffix[i] ：以 i-1 结尾的最大后缀和（可以为 0，表示左边不取）。 leftSuffix[0]=0 ， leftSuffix[i] = max(0, leftSuffix[i-1] + nums[i-1]) 。 rightPrefix[i] ：以 i 开头的最大前缀和（至少一个元素）。 rightPrefix[n]=-inf ，从右向左计算： rightPrefix[i] = max(nums[i], nums[i] + rightPrefix[i+1]) ，但注意至少取一个元素，所以不能为 0。不过在我们的跨越三部分公式中，右边一段可以没有，所以我们可以定义 rightPrefix[i] 为从 i 开始的最大前缀和（允许为空，和为 0）。但为了统一，我们允许右边为空，即 rightPrefix[n]=0 ， rightPrefix[i] = max(0, nums[i] + rightPrefix[i+1]) ？不对，如果右边全是负数，我们应该不取，即为 0。所以定义 rightPrefix[i] 为从 i 开始的最大前缀和（非空），但我们可以用类似 leftSuffix 的方式，定义 rightGain[i] 为从 i 开始的最大前缀和（允许为空，即 0）。但公式中是 rightPrefix[r+1] ，它可能为 0。 我们定义 rightGain[i] 为原数组从 i 到末尾的最大前缀和（允许为空，和为 0）。 rightGain[n]=0 ， rightGain[i] = max(0, nums[i] + rightGain[i+1]) 。 注意：这样如果右边一段全负，就不取，和为 0。 9. 算法步骤 预处理： leftMax[i] ：前 i 个元素的最大子段和。 rightMax[i] ：后 n-i 个元素的最大子段和。 leftSuffix[i] ：以 i-1 结尾的最大后缀和（非负，因为可以不取左边）。 rightGain[i] ：从 i 开始的最大前缀和（非负）。 初始化答案 ans 为不翻转的最大子段和（即 leftMax[n] ）。 枚举左端点 l ： 初始化 cur=0 , midMax=0 （因为 [l, l-1] 区间为空）。 从 l 到 n-1 枚举右端点 r ： 用 Kadane 更新 cur = max(cur + nums[r], nums[r]) ， midMax = max(midMax, cur) 。 计算翻转 [l, r] 的候选值： candidate = leftSuffix[l] + midMax + rightGain[r+1] 。 同时考虑不跨越的情况： candidate = max(candidate, leftMax[l], rightMax[r+1]) 。 更新 ans = max(ans, candidate) 。 返回 ans 。 10. 边界处理 当 l=0 时， leftSuffix[0]=0 ，左边为空。 当 r=n-1 时， rightGain[n]=0 ，右边为空。 注意 rightMax[r+1] 当 r+1=n 时，表示右边为空，最大子段和为负无穷（但右边为空时，我们不考虑右边单独一段，因为这种情况已经被 leftMax[l] 覆盖了）。但为了统一，我们定义 rightMax[n] = -inf （用很负数代替），这样在比较时，如果右边全负， rightMax[n] 会是负数，但 leftSuffix[l] + midMax + rightGain[r+1] 可能更大。 11. 示例验证 以 nums = [1, -2, 3, 4] 为例： 预处理： leftSuffix = [0, 1, 0, 3, 7] （长度为5，leftSuffix[ 0]=0, leftSuffix[ 1]=max(0,0+1)=1, leftSuffix[ 2]=max(0,1+(-2))=0, leftSuffix[ 3]=max(0,0+3)=3, leftSuffix[ 4 ]=max(0,3+4)=7）。 rightGain = [7, 7, 7, 4, 0] （从右到左：rightGain[ 4]=0, rightGain[ 3]=max(0,4+0)=4, rightGain[ 2]=max(0,3+4)=7, rightGain[ 1 ]=max(0,-2+7)=5? 等等，我们重新算： 从右到左，rightGain[ i] = max(0, nums[ i] + rightGain[ i+1 ])。 rightGain[ 4 ]=0, i=3: rightGain[ 3 ]=max(0,4+0)=4, i=2: rightGain[ 2 ]=max(0,3+4)=7, i=1: rightGain[ 1 ]=max(0,-2+7)=5, i=0: rightGain[ 0 ]=max(0,1+5)=6。 但注意，rightGain[ i] 是从 i 开始的最大前缀和（非负），所以应该是允许从 i 开始取一段连续子数组，和最大且非负。但这样计算实际上是允许任意长度（包括0），所以是最大前缀和（非负）。但我们的公式中，rightGain[ r+1] 是右边一段的最大和（非负），所以应该是从 r+1 开始的最大子段和（非负）。所以我们用 rightGain[ i ] 表示从 i 开始的最大子段和（非负）。但最大子段和不一定从 i 开始，可能从后面开始。所以我们需要的是从 i 开始的最大前缀和（非负），而不是最大子段和。 重新定义： rightPrefixMax[i] 为从 i 开始的最大前缀和（非负）。 rightPrefixMax[ 4 ]=0, i=3: max(0,4)=4, i=2: max(0,3, 3+4)=7, 等等，前缀和必须从 i 开始连续，所以应该是 rightStartMax[i] = max(0, nums[i], nums[i]+nums[i+1], ...) 的最大值，但可以递推： rightStartMax[i] = max(0, nums[i] + rightStartMax[i+1]) 。 因为如果从 i 开始取一段，要么不取（0），要么取 nums[ i ] 以及后面的一段（但必须连续从 i 开始）。所以递推式正确。 我们重新计算： rightStartMax[ 4 ]=0, i=3: max(0, 4+0)=4, i=2: max(0, 3+4)=7, i=1: max(0, -2+7)=5, i=0: max(0, 1+5)=6。 但注意，从 i=1 开始，取 [-2,3,4] 和是5，没错。 但我们的公式中，右边一段是原数组从 r+1 开始的一段前缀（在新数组中连续），所以应该是从 r+1 开始的最大前缀和（非负），所以用 rightStartMax 是对的。 但注意，我们之前公式中写的是 rightGain[ r+1]，就是 rightStartMax[ r+1 ]。 枚举 l=0: cur=0, midMax=0 r=0: cur=max(0+1,1)=1, midMax=1, candidate = leftSuffix[ 0]+midMax+rightStartMax[ 1] = 0+1+5=6, 同时与 leftMax[ 0]（前0个最大子段和，设为 -inf）和 rightMax[ 1 ]（后3个最大子段和，即7）比较，取 max(6,7)=7，ans=7。 r=1: cur=max(1+(-2),-2)=-1, midMax=1（不变），candidate=0+1+rightStartMax[ 2]=1+7=8, 与 leftMax[ 0] 和 rightMax[ 2 ]（后2个最大子段和，即7）比较，max(8,7)=8，ans=8。 r=2: cur=max(-1+3,3)=3, midMax=max(1,3)=3, candidate=0+3+rightStartMax[ 3 ]=3+4=7, max(7,7)=7，ans=8。 r=3: cur=3+4=7, midMax=7, candidate=0+7+rightStartMax[ 4]=7+0=7, max(7,rightMax[ 4 ]（后0个为 -inf）)=7，ans=8。 枚举 l=1,2,3 等，都不会超过8。 最终 ans=8，正确。 12. 时间复杂度 预处理 O(n)，枚举 l 和 r 是 O(n²)，在 n≤10^4 时可能超时。但我们可以优化： 注意到固定 l，我们只需要一次遍历 r 并维护 midMax（区间 [ l, r ] 的最大子段和），这是 O(n) 的，所以总 O(n²)。 n=10^4 时，O(n²) 是 10^8，可能勉强过（在优化良好的情况下），但通常希望 O(n)。 有没有 O(n) 方法？ 我们可以考虑不枚举区间，而是计算“翻转一次”带来的最大增益。 但本题通常的 O(n) 解法是： 定义 f[i] 为以 i 结尾的最大子段和（不翻转）。 定义 g[i] 为以 i 开头的最大子段和（不翻转）。 定义 h[i] 为在 i 处翻转（即翻转的区间以 i 为左端点或右端点）能得到的最大增益。 但更简单的 O(n) 解法是： 计算不翻转时的最大子段和 maxSum 。 然后计算翻转一个子数组能增加的最大值。 翻转一个子数组 [l, r] 相当于，我们找到两个不相交的子数组：一个在左边（以 l-1 结尾），一个在右边（以 r+1 开头），中间夹着原数组的 [l, r] 段，但顺序反转。但顺序反转不影响和，所以中间段的和就是原数组 [l, r] 的和。 那么新数组中的子段和就是：左边后缀和 + 中间段和 + 右边前缀和。 我们希望最大化这个值。 我们可以枚举中间段的两个端点，但可以转换成： 对于每个位置 i，计算以 i 结尾的最大后缀和 leftSuffix[i] ，和以 i 开头的最大前缀和 rightPrefix[i] 。 然后，问题变成找两个位置 l <= r ，使得 leftSuffix[l] + (sum(l, r)) + rightPrefix[r+1] 最大。 令 total = leftSuffix[l] + rightPrefix[r+1] + sum(l, r) 。 我们可以固定 r，求最大的 leftSuffix[l] + sum(l, r) ，其中 l ≤ r。 定义 bestLeft[r] = max_{0<=l<=r} (leftSuffix[l] + sum(l, r)) 。 而 sum(l, r) = prefixSum[r+1] - prefixSum[l] ，其中 prefixSum[i] 是前 i 个元素的和。 所以 leftSuffix[l] + sum(l, r) = leftSuffix[l] - prefixSum[l] + prefixSum[r+1] 。 对于固定的 r， prefixSum[r+1] 是常数，所以我们只需要最大化 leftSuffix[l] - prefixSum[l] ，记作 val[l] 。 那么 bestLeft[r] = prefixSum[r+1] + max_{0<=l<=r} val[l] 。 我们可以从左到右扫描，维护 maxVal = max(val[l]) 。 然后对于每个 r，候选值为 bestLeft[r] + rightPrefix[r+1] 。 但注意， leftSuffix[l] 是以 l-1 结尾的最大后缀和，所以 leftSuffix[0]=0 ， leftSuffix[l] = max(0, leftSuffix[l-1] + nums[l-1]) 。 val[l] = leftSuffix[l] - prefixSum[l] 。 然后 bestLeft[r] = prefixSum[r+1] + max_{0<=l<=r} val[l] 。 那么翻转区间 [l, r] 对应的新子段和为 bestLeft[r] + rightPrefix[r+1] 。 但这样我们假定了子段包含整个翻转区间 [l, r] 。 如果子段只包含翻转区间的一部分，会怎样？ 实际上，我们之前已经分析过，新数组的最大子段和可能是三部分：左边后缀、中间一段（原数组 [l, r] 的子段）、右边前缀。 如果我们设中间一段是原数组的 [x, y] （l ≤ x ≤ y ≤ r），那么新子段和为 leftSuffix[l] + sum(x, y) + rightPrefix[r+1] 。 为了最大化，我们会选择 [x, y] 为 [l, r] 内的最大子段和。 所以我们需要的是 leftSuffix[l] + maxSubarray(l, r) + rightPrefix[r+1] 。 但这样又回到了需要区间最大子段和的问题。 然而，我们可以考虑另一种思路： 翻转区间 [l, r] 后，新数组的最大子段和等价于： max( leftMax[l], rightMax[r+1], leftSuffix[l] + maxSubarray(l, r) + rightPrefix[r+1] ) 。 其中 maxSubarray(l, r) 是区间 [l, r] 的最大子段和。 我们可以枚举 l，然后随着 r 增大，用 Kadane 维护 maxSubarray(l, r) 。 这就是我们之前的 O(n²) 算法。 对于 n=10^4，O(n²) 可能过不了。但我们可以尝试优化常数，或者寻求 O(n) 解法。 13. 最终采用的 O(n) 解法 实际上，这个问题可以转化为： 不翻转的最大子段和记为 ans 。 翻转一次相当于，我们可以选择两个不相交的子数组，然后拼接起来（因为翻转中间段相当于把中间段反转，但拼接时中间段和不变，所以可以看作两个子数组中间夹着一个反转段，但反转段本身可以是一个子数组）。 更准确地说，翻转区间 [l, r] 后，新数组中的一个子段可以看作由三部分组成：原数组的一个后缀（在 l 之前）、原数组的一个子数组（在 [l, r] 内）、原数组的一个前缀（在 r 之后）。 我们想要最大化这三段的和。 定义 leftBest[i] 为原数组前 i 个元素中，两段不相交子数组的最大和，其中一段以 i-1 结尾，另一段在其左边。 但这样太复杂。 其实有一个巧妙的 O(n) 解法： 翻转一个子数组等价于，我们可以选择两个不相交的子数组，然后让它们的顺序交换（即先取右边的，再取左边的）。 但翻转是反转一个连续段，所以新子段可以是：原数组的一个子数组，或者两段不相交的子数组的和（但顺序是右边的先，左边的后）。 所以问题转化为：求原数组的两个不相交子数组的最大和，但顺序可以交换（即我们可以先取后面一段，再取前面一段）。 因为翻转一个区间，相当于把后面一段放到前面，前面一段放到后面，中间的反转段相当于一个子数组。 但注意，如果只取两段，中间的反转段可能为空，即我们只是交换了两段的位置。 所以翻转一次能得到的最大子段和，等于以下两种情况的最大值： 原数组的最大子段和（不翻转）。 原数组的两段不相交子数组的最大和，但考虑顺序（即可以后一段在前，前一段在后）。 因为如果我们取两段不相交子数组，我们可以通过翻转它们之间的部分来使它们相邻。 具体地，设两段子数组的起始和结束位置为 [l1, r1] 和 [l2, r2] ，且 r1 < l2 。 翻转区间 [r1+1, l2-1] ，则新数组中这两段就相邻了，且顺序变为先 [l2, r2] 后 [l1, r1] 。 所以新子段和为两段和相加。 因此，问题等价于求原数组的两段不相交子数组的最大和。 这是一个经典问题：最大两段子段和。 但注意，两段子数组的顺序可以交换，所以我们求的是“两段不相交子数组的最大和”，不考虑顺序。 求法： 从左到右求 left[i] 表示前 i 个元素的最大子段和。 从右到左求 right[i] 表示后 n-i 个元素的最大子段和。 然后枚举分割点 i， left[i] + right[i] 的最大值就是两段不相交子数组的最大和。 但这样两段顺序是左前右后。 如果交换顺序，即右前左后，那么相当于求 left[i] 和 right[i] 但方向相反。 但两段不相交子数组的最大和，与顺序无关，因为两段的和是加法交换的。 所以直接求 max_{i} (left[i] + right[i]) 即可。 但注意，两段可能有一段为空，这时就是一段子数组的情况。 所以翻转一次的最大子段和 = max(一段的最大子段和, 两段不相交子数组的最大和) 。 但这样对吗？我们检查示例1： 原数组 [1, -2, 3, 4] ，一段最大子段和是7（ [3,4] ）。 两段不相交子数组最大和：可以取 [1] 和 [3,4] ，和为8。 所以答案是8，正确。 示例2： [-1, -1] ，一段最大子段和是-1，两段最大和是-2（取两个-1），所以最大是-1，正确。 再测试一个数组 [1,2,3,-4,5] ，一段最大是6（ [1,2,3] ），两段可以取 [1,2,3] 和 [5] ，和是6+5=11，翻转区间 [3,3] （即-4）使得 [1,2,3] 和 [5] 相邻，新数组为 [1,2,3,5,-4] ，最大子段和为11，正确。 所以这个转换是正确的。 14. 算法总结 求原数组的最大子段和 singleMax （用 Kadane）。 求两段不相交子数组的最大和 doubleMax ： 从左到右计算 left[i] ：前 i 个元素的最大子段和（ left[0]=-inf ，用 Kadane 更新）。 从右到左计算 right[i] ：后 n-i 个元素的最大子段和（ right[n]=-inf ，用 Kadane 更新）。 遍历每个分割点 i（0<=i<=n）， doubleMax = max(doubleMax, left[i] + right[i]) 。 答案 = max(singleMax, doubleMax) 。 注意： left[i] 是前 i 个元素的最大子段和（子段不一定以 i-1 结尾）， right[i] 是后 n-i 个元素的最大子段和。 这样， left[i] + right[i] 表示两段不相交子数组的和，一段在前 i 个元素中，一段在后 n-i 个元素中。 但两段可能有一段为空，所以 doubleMax 至少是 singleMax 。 所以答案就是 doubleMax 。 但注意，如果全为负数， doubleMax 可能是两个负数相加，小于 singleMax （最大单个元素），但 left[i] 和 right[i] 在计算时，Kadane 算法会处理全负数情况， left[i] 是前 i 个元素的最大子段和（至少一个元素），所以 doubleMax 可能小于 singleMax ，取 max 即可。 15. 时间复杂度 O(n)，空间 O(n)（可以优化到 O(1)）。 16. 最终算法步骤 初始化 singleMax 为 Kadane 算法求整个数组的最大子段和。 计算 left 数组： left[0] = -inf ， cur=0 , maxSoFar=-inf ，遍历 i 从 0 到 n-1： cur = max(cur + nums[i], nums[i]) ， maxSoFar = max(maxSoFar, cur) ， left[i+1] = maxSoFar 。 计算 right 数组： right[n] = -inf ， cur=0 , maxSoFar=-inf ，遍历 i 从 n-1 到 0： cur = max(cur + nums[i], nums[i]) ， maxSoFar = max(maxSoFar, cur) ， right[i] = maxSoFar 。 初始化 doubleMax = -inf ，遍历 i 从 0 到 n： doubleMax = max(doubleMax, left[i] + right[i]) 。 返回 max(singleMax, doubleMax) 。 17. 示例验证 nums = [1, -2, 3, 4] singleMax: Kadane 得到 7（3+4）。 left: [ -inf, 1, 1, 3, 7 ] right: 从右到左： 初始化 cur=0, maxSoFar=-inf i=3: cur=4, maxSoFar=4, right[ 3 ]=4 i=2: cur=max(4+3,3)=7, maxSoFar=7, right[ 2 ]=7 i=1: cur=max(7+(-2),-2)=5, maxSoFar=7, right[ 1 ]=7 i=0: cur=max(5+1,1)=6, maxSoFar=7, right[ 0 ]=7 所以 right = [ 7,7,7,4,-inf]（right[ 4 ]未定义，但用 -inf） 遍历 i: i=0: left[ 0]+right[ 0 ] = -inf+7 = -inf i=1: 1+7=8 i=2: 1+7=8 i=3: 3+4=7 i=4: 7+(-inf) = -inf doubleMax=8 答案 max(7,8)=8，正确。 18. 边界情况 全负数： [-1, -2] ，singleMax=-1，left=[ -inf, -1, -1]，right=[ -1, -2, -inf ]，doubleMax=max(-inf, -1-2=-3, -1+(-inf)=-inf) = -3，答案 max(-1,-3)=-1，正确。 单个元素： [5] ，singleMax=5，left=[ -inf,5]，right=[ 5,-inf ]，doubleMax=5+(-inf)=-inf，答案5，正确。 19. 总结 本题的关键是将“翻转一个子数组”转化为“求两段不相交子数组的最大和”，因为翻转后，我们可以将两段原本不相交的子数组通过翻转中间部分而相邻，从而合并成一段。 因此，问题简化为求原数组的两段不相交子数组的最大和，这可以用前后缀分解在线性时间内解决。 这样，我们就得到了一个 O(n) 时间、O(n) 空间的优美解法。