区间动态规划例题：最大子数组和问题（允许最多翻转一个子数组）

题目描述
给定一个整数数组nums，你可以选择翻转数组的任意一个连续子数组（翻转操作最多只能执行一次），然后返回可能得到的最大子数组和。

示例：
输入：nums = [1, -2, 3, -2, 4]
输出：9
解释：翻转子数组[-2, 3, -2]得到[1, 3, -2, 3, 4]，最大子数组和为3 + (-2) + 3 + 4 = 9

解题过程

这个问题可以分解为两个部分：基础的最大子数组和问题，以及翻转操作带来的影响。我们将使用动态规划来跟踪多个关键量。

步骤1：问题分析

• 如果不进行翻转，就是标准的最大子数组和问题（Kadane算法）
• 翻转一个子数组相当于将某个区间[i, j]的元素顺序反转
• 翻转的效果相当于将该区间的"最大子数组和"计算方向反转
• 关键思路：翻转区间[i, j]相当于将原问题分解为三部分：
  1. 区间[0, i-1]的正常最大子数组和
  2. 区间[i, j]的反转部分（即该区间的最小子数组和，反转后变成最大）
  3. 区间[j+1, n-1]的正常最大子数组和

步骤2：定义状态变量
我们需要定义四个动态规划数组：

1. left_max[i]：以i结尾的最大子数组和（从左到右）
2. right_max[i]：以i开始的最大子数组和（从右到左）
3. left_min[i]：以i结尾的最小子数组和（从左到右）
4. right_min[i]：以i开始的最小子数组和（从右到左）

步骤3：状态转移方程

从左到右计算：

• left_max[i] = max(nums[i], left_max[i-1] + nums[i])
• left_min[i] = min(nums[i], left_min[i-1] + nums[i])

从右到左计算：

• right_max[i] = max(nums[i], right_max[i+1] + nums[i])
• right_min[i] = min(nums[i], right_min[i+1] + nums[i])

步骤4：考虑翻转操作
对于每个可能的分割点i（0 ≤ i ≤ n）：

• 不翻转任何区间：max_sum = max(max_sum, left_max[i])
• 翻转区间[0, i]：max_sum = max(max_sum, -left_min[i])（如果i=0）
• 翻转区间[i, n-1]：max_sum = max(max_sum, -right_min[i])（如果i=n-1）
• 翻转区间中间部分：对于每个分割点i，考虑翻转[i, j]区间

步骤5：优化计算
我们可以通过预处理来避免O(n²)的复杂度：

max_sum = max(left_max)  # 不翻转的情况

# 考虑翻转区间[0, j]
for j in range(n):
    max_sum = max(max_sum, -left_min[j] + (right_max[j+1] if j+1 < n else 0))

# 考虑翻转区间[i, n-1]
for i in range(n):
    max_sum = max(max_sum, (left_max[i-1] if i-1 >= 0 else 0) - right_min[i])

# 考虑翻转中间区间[i, j]
for i in range(1, n):
    max_sum = max(max_sum, left_max[i-1] - (right_min[i] - (right_max[i+1] if i+1 < n else 0)))

步骤6：完整算法实现

def maxSubarraySumAfterOneFlip(nums):
    if not nums:
        return 0
    
    n = len(nums)
    if n == 1:
        return max(nums[0], -nums[0])  # 可以选择翻转单个元素
    
    # 初始化DP数组
    left_max = [0] * n
    left_min = [0] * n
    right_max = [0] * n
    right_min = [0] * n
    
    # 从左到右计算
    left_max[0] = left_min[0] = nums[0]
    for i in range(1, n):
        left_max[i] = max(nums[i], left_max[i-1] + nums[i])
        left_min[i] = min(nums[i], left_min[i-1] + nums[i])
    
    # 从右到左计算
    right_max[n-1] = right_min[n-1] = nums[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(nums[i], right_max[i+1] + nums[i])
        right_min[i] = min(nums[i], right_min[i+1] + nums[i])
    
    # 计算最大和
    max_sum = max(left_max)  # 不翻转的情况
    
    # 考虑各种翻转情况
    for i in range(n):
        # 翻转[0, i]区间
        flip_sum = -left_min[i] + (max(0, right_max[i+1]) if i+1 < n else 0)
        max_sum = max(max_sum, flip_sum)
        
        # 翻转[i, n-1]区间
        flip_sum = (max(0, left_max[i-1]) if i-1 >= 0 else 0) - right_min[i]
        max_sum = max(max_sum, flip_sum)
    
    return max_sum

步骤7：复杂度分析

• 时间复杂度：O(n)，我们进行了4次线性扫描
• 空间复杂度：O(n)，使用了4个辅助数组

这个算法巧妙地利用了最大子数组和与最小子数组和之间的关系，通过一次翻转操作将最小和区域转换为最大和区域，从而得到可能的最大子数组和。