线性动态规划：最大子数组和的变种——最多允许翻转一个子数组的最大子数组和

题目描述
给定一个整数数组nums，你可以选择翻转它的任意一个连续子数组（即将该子数组的元素顺序完全反转）。翻转操作只能执行一次（也可以不翻转）。请计算翻转后可能得到的最大子数组和。

注意：

• 子数组是连续的
• 翻转操作是可选的，可以不执行任何翻转
• 需要返回可能的最大子数组和

示例：
输入：nums = [1, -2, 3, -4, 5, -3, 2]
输出：11
解释：翻转子数组[-4, 5]得到[1, -2, 3, 5, -4, -3, 2]，最大子数组和为3+5-4-3+2+1？实际上最优解是翻转子数组[-4, 5, -3]得到[1, -2, 3, -3, 5, -4, 2]，最大子数组和为3-3+5=5？让我们重新计算...

解题过程

步骤1：理解问题本质
这个问题可以分解为两个部分：

1. 不进行翻转时的最大子数组和（标准最大子数组和问题）
2. 翻转某个子数组后能获得的最大子数组和

关键洞察：翻转一个子数组相当于将原数组分成三部分：[左部分] + [翻转部分] + [右部分]，翻转后最大子数组和可能跨越这三部分。

步骤2：基础最大子数组和
首先回顾标准的最大子数组和问题（Kadane算法）：

def maxSubArray(nums):
    max_sum = nums[0]
    current_sum = nums[0]
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    return max_sum

步骤3：预处理关键数组
我们需要预处理四个数组来帮助我们计算翻转后的最大子数组和：

1. left_max[i]：原数组从开头到位置i（包含）的最大子数组和
2. right_max[i]：原数组从位置i（包含）到结尾的最大子数组和
3. left_sum[i]：原数组从开头到位置i（包含）的累计和
4. right_sum[i]：原数组从位置i（包含）到结尾的累计和

步骤4：计算翻转后的最大和
对于每个可能的翻转区间[i, j]，翻转后的最大子数组和可以表示为：

max_sum = max(
    left_max[i-1] + (right_sum[j] - left_sum[i-1]) + right_max[j+1],
    ...
)

更精确地说，翻转区间[i, j]后，最大子数组和可能出现在：

• 完全在左部分：left_max[i-1]
• 跨越左部分和翻转部分：left_max[i-1] + (区间[i, j]的累计和)
• 完全在翻转部分：区间[i, j]的累计和（翻转后不变）
• 跨越翻转部分和右部分：(区间[i, j]的累计和) + right_max[j+1]
• 跨越所有三部分：left_max[i-1] + (区间[i, j]的累计和) + right_max[j+1]

步骤5：动态规划实现

def maxSubarraySumCircular(nums):
    n = len(nums)
    if n == 0: return 0
    
    # 预处理数组
    left_max = [0] * n
    right_max = [0] * n
    left_sum = [0] * n
    right_sum = [0] * n
    
    # 计算left_sum和left_max
    left_sum[0] = nums[0]
    left_max[0] = nums[0]
    current_sum = nums[0]
    for i in range(1, n):
        left_sum[i] = left_sum[i-1] + nums[i]
        current_sum = max(nums[i], current_sum + nums[i])
        left_max[i] = max(left_max[i-1], current_sum)
    
    # 计算right_sum和right_max
    right_sum[n-1] = nums[n-1]
    right_max[n-1] = nums[n-1]
    current_sum = nums[n-1]
    for i in range(n-2, -1, -1):
        right_sum[i] = right_sum[i+1] + nums[i]
        current_sum = max(nums[i], current_sum + nums[i])
        right_max[i] = max(right_max[i+1], current_sum)
    
    # 计算不翻转的最大子数组和
    no_flip_max = left_max[n-1]
    
    # 计算翻转后的最大子数组和
    flip_max = no_flip_max
    for i in range(n):
        for j in range(i, n):
            # 计算区间[i, j]的累计和
            interval_sum = left_sum[j] - (left_sum[i-1] if i > 0 else 0)
            
            # 计算翻转后的可能最大和
            left_part = left_max[i-1] if i > 0 else 0
            right_part = right_max[j+1] if j < n-1 else 0
            
            current_max = max(
                left_part,                    # 只在左部分
                interval_sum,                 # 只在翻转部分  
                right_part,                   # 只在右部分
                left_part + interval_sum,     # 左部分+翻转部分
                interval_sum + right_part,    # 翻转部分+右部分
                left_part + interval_sum + right_part  # 所有三部分
            )
            
            flip_max = max(flip_max, current_max)
    
    return flip_max

步骤6：优化时间复杂度
上面的解法是O(n²)的，我们可以优化到O(n)：

关键观察：翻转区间[i, j]相当于将原数组的最大子数组和问题转化为：

max_sum = max(no_flip_max, max_{0≤i≤j<n} (left_max[i-1] + (区间[j]到[i]的累计和) + right_max[j+1]))

更高效的O(n)解法：

def maxSubarraySumWithOneFlip(nums):
    n = len(nums)
    if n == 0: return 0
    
    # 标准最大子数组和
    no_flip = nums[0]
    current = nums[0]
    for i in range(1, n):
        current = max(nums[i], current + nums[i])
        no_flip = max(no_flip, current)
    
    # 计算前缀和
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + nums[i]
    
    # 计算left_max和right_max
    left_max = [0] * n
    right_max = [0] * n
    
    left_max[0] = nums[0]
    current = nums[0]
    for i in range(1, n):
        current = max(nums[i], current + nums[i])
        left_max[i] = max(left_max[i-1], current)
    
    right_max[n-1] = nums[n-1]
    current = nums[n-1]
    for i in range(n-2, -1, -1):
        current = max(nums[i], current + nums[i])
        right_max[i] = max(right_max[i+1], current)
    
    # 计算翻转后的最大和
    flip_max = no_flip
    for i in range(1, n):
        # 翻转区间[0, i-1]
        flip_max = max(flip_max, right_max[i] + max(0, prefix_sum[i] - min(prefix_sum[0:i])))
    
    return flip_max

步骤7：最终优化版本
这是最高效的O(n)解法：

def maxSubarraySumWithOneFlip(nums):
    n = len(nums)
    if n == 0: return 0
    
    # 计算不翻转的最大子数组和
    no_flip = nums[0]
    current = nums[0]
    for i in range(1, n):
        current = max(nums[i], current + nums[i])
        no_flip = max(no_flip, current)
    
    # 计算前缀和
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    
    # 计算右侧最大子数组和
    right_max = [0] * (n + 1)
    right_max[n] = 0
    current = 0
    for i in range(n-1, -1, -1):
        current = max(nums[i], current + nums[i])
        right_max[i] = max(right_max[i+1], current) if i < n-1 else current
    
    # 计算翻转后的最大和
    flip_max = no_flip
    min_prefix = 0
    
    for i in range(1, n + 1):
        # 翻转区间[0, i-1]后，最大子数组和 = right_max[i] + (prefix[i] - min_prefix)
        flip_max = max(flip_max, right_max[i] + (prefix[i] - min_prefix))
        min_prefix = min(min_prefix, prefix[i])
    
    return flip_max

这个算法的时间复杂度是O(n)，空间复杂度也是O(n)，能够高效解决这个问题。