1186. Maximum Subarray Sum with One Deletion¶
题目信息¶
- 题号:
1186
- 难度:
Medium
- 主题:
数组、动态规划、最大子数组
- 原题:
- 重点:
先选择非空连续子数组,再允许删除其中至多一个元素;删除后仍必须至少保留一个元素
题目重述¶
给定整数数组 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 且不删除即可得到最大总和。