| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
true |
困难 |
|
给你一个整数数组 nums 。
你可以对数组执行以下操作 至多 一次：
- 选择
nums中存在的 任意 整数X，确保删除所有值为X的元素后剩下数组 非空 。 - 将数组中 所有 值为
X的元素都删除。
请你返回 所有 可能得到的数组中 最大 子数组 和为多少。
示例 1：
输入：nums = [-3,2,-2,-1,3,-2,3]
输出：7
解释：
我们执行至多一次操作后可以得到以下数组：
- 原数组是
nums = [-3, 2, -2, -1, 3, -2, 3]。最大子数组和为3 + (-2) + 3 = 4。 - 删除所有
X = -3后得到nums = [2, -2, -1, 3, -2, 3]。最大子数组和为3 + (-2) + 3 = 4。 - 删除所有
X = -2后得到nums = [-3, 2, -1, 3, 3]。最大子数组和为2 + (-1) + 3 + 3 = 7。 - 删除所有
X = -1后得到nums = [-3, 2, -2, 3, -2, 3]。最大子数组和为3 + (-2) + 3 = 4。 - 删除所有
X = 3后得到nums = [-3, 2, -2, -1, -2]。最大子数组和为 2 。
输出为 max(4, 4, 7, 4, 2) = 7 。
示例 2：
输入：nums = [1,2,3,4]
输出：10
解释：
最优操作是不删除任何元素。
提示：
1 <= nums.length <= 105-106 <= nums[i] <= 106