数组查询

Description

Given an array, the task is to complete the function which finds the maximum sum subarray, where you may remove at most one element to get the maximum sum.

思路

1. 暴力（O(n^2)）

移除数组中的一个负数，然后求数组的最大子数组；对每一个负数执行上述的操作，取最大值。

怎么求数组的最大子数组呢？

遍历数组，两个变量 当前累加值cur_sum，最大子数组值 ans

for i in [0, 1, ... n-1]
    cur_sum += nums[i]
    ans = max(cur_sum, ans)
    cur_sum = max(cur_sum, 0)

2. 累加左边，累加右边（O(n))

既然可以删除一个数，那换一种思路考虑就是，假设删除的数位置是i，那只需要找出i左边连续的和最大的子数组与右边连续和最大的子数组，两者相加就是结果。这里要注意的是连续，因为我们删除i位置的数，所以左右的数组都是与i连续的。

如果对于每个i都去计算左边与右边最大子数组的话，就会有很多重复计算，时间复杂度还是O(n^2)。

因此我们可以首先算出两个数组left, right 存放每个位置左边有右边最大子数组的和，然后遍历每个位置，取左边加右边最大的值。

python

def solve(nums):
    if max(nums) <= 0:
        return max(nums)
    n = len(nums)
    left = [0] * n
    for i in range(len(nums)-1):
        left[i+1] = max(nums[i]+left[i], 0)

    right = [0] * n
    for i in range(1, len(nums))[::-1]:
        right[i-1] = max(nums[i]+right[i], 0)

    ans = float('-inf')
    for i in range(n):
        ans = max(ans, left[i]+right[i], left[i] + nums[i] + right[i])
    return ans