1186. Maximum Subarray Sum with One Deletion

题目信息

题号:

1186

难度:

Medium

主题:

数组、动态规划、最大子数组

原题:

LeetCode 1186

重点:

先选择非空连续子数组,再允许删除其中至多一个元素;删除后仍必须至少保留一个元素

题目重述

给定整数数组 arr。选择一个非空连续子数组,并可以从该子数组中删除至多一个元素;也允许不删除。

删除后剩余元素仍按原顺序计算总和,并且至少保留一个元素。请返回能够得到的最大总和。

1 <= arr.length <= 10^5,-10^4 <= arr[i] <= 10^4。

自建示例

删除中间负数连接两侧正数:

输入:arr = [2,-5,4,3]
输出:9
解释:选择整个数组并删除 -5,剩余元素和为 2 + 4 + 3 = 9。

全部元素为负数:

输入:arr = [-4,-2,-7]
输出:-2
解释:必须保留至少一个元素,选择单独的 -2 且不删除即可得到最大总和。