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)）
移除數組中的一個負數匠楚，然后求數組的最大子數組帝火；對每一個負數執(zhí)行上述的操作拱绑，取最大值折柠。
怎么求數組的最大子數組呢蹈集？
遍歷數組选侨，兩個變量 當前累加值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左邊連續(xù)的和最大的子數組與右邊連續(xù)和最大的子數組聘萨，兩者相加就是結果竹椒。這里要注意的是連續(xù)，因為我們刪除i位置的數米辐，所以左右的數組都是與i連續(xù)的胸完。
如果對于每個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
