448最大连续子数组和问题

题解

问题描述

给定一个整数数组，允许最多进行一次修改，将任意一个元素修改为任意给定的值 x。求经过修改后，能够得到的连续子数组的最大和。

解题思路

一个比较经典的动态规划，需要注意的是题目要求的是必须恰好修改一次。

1. 特殊情况处理：

   • 当数组长度为 1 时，返回 x。
   • 如果数组中所有元素都小于等于 0，返回数组中最大的元素和 x 中的较大者。

2. 前缀和计算：

   • 使用后缀数组 suf，其中 suf[i] 表示从第 i 个元素开始的最大子数组和。
   • 从数组末尾向前遍历，更新 suf[i] 为 suf[i+1] + a[i-1] 和 0 的较大值。

3. 遍历数组并计算结果：

   • 使用变量 f 来记录当前的最大子数组和。
   • 对于每个位置 i，计算将 a[i-1] 修改为 x 后的最大子数组和，更新结果 res。
   • 更新 f 为 f + a[i-1] 和 0 的较大值，以便下一次迭代使用。

代码解析

def solution(n: int, x: int, a: list) -> int:
    if n == 1: return x
    if all(i <= 0 for i in a):
        return max(a + [x])
    suf = [0] * (n + 2)
    for i in range(n, 0, -1):
        suf[i] = max(suf[i + 1] + a[i - 1], 0)
    res = f = 0
    for i in range(1, n + 1):
        res = max(res, f + suf[i + 1] + x, f, suf[i + 1])
        f = max(f + a[i - 1], 0)

    return res


if __name__ == '__main__':
    print(solution(n = 5, x = 10, a = [5, -1, -5, -3, 2]) == 15)
    print(solution(n = 2, x = -3, a = [-5, -2]) == -2)
    print(solution(n = 6, x = 10, a = [4, -2, -11, -1, 4, -1]) == 15)

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组的长度。需要两次遍历数组。
• 空间复杂度：O(n)，用于存储后缀数组 suf。