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)）

移除數(shù)組中的一個(gè)負(fù)數(shù)，然后求數(shù)組的最大子數(shù)組；對(duì)每一個(gè)負(fù)數(shù)執(zhí)行上述的操作，取最大值。

怎么求數(shù)組的最大子數(shù)組呢？

遍歷數(shù)組，兩個(gè)變量 當(dāng)前累加值cur_sum，最大子數(shù)組值 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))

既然可以刪除一個(gè)數(shù)，那換一種思路考慮就是，假設(shè)刪除的數(shù)位置是i，那只需要找出i左邊連續(xù)的和最大的子數(shù)組與右邊連續(xù)和最大的子數(shù)組，兩者相加就是結(jié)果。這里要注意的是連續(xù)，因?yàn)槲覀儎h除i位置的數(shù)，所以左右的數(shù)組都是與i連續(xù)的。

如果對(duì)于每個(gè)i都去計(jì)算左邊與右邊最大子數(shù)組的話，就會(huì)有很多重復(fù)計(jì)算，時(shí)間復(fù)雜度還是O(n^2)。

因此我們可以首先算出兩個(gè)數(shù)組left, right 存放每個(gè)位置左邊有右邊最大子數(shù)組的和，然后遍歷每個(gè)位置，取左邊加右邊最大的值。

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