Maximize Subarray Sum After Removing All Occurrences of One Element
You are given an integer array nums.
You can do the following operation on the array at most once:
- Choose any integer
xsuch thatnumsremains non-empty on removing all occurrences ofx. - Remove all occurrences of
xfrom the array.
Return the maximum subarray sum across all possible resulting arrays.
Example 1
Input
nums = [-3,2,-2,-1,3,-2,3]Output
7Deleting all occurrences of
-2 gives [-3, 2, -1, 3, 3], whose maximum subarray sum is 7, which is best among all possible resulting arrays.Example 2
Input
nums = [1,2,3,4]Output
10It is optimal to not perform any operations, so the maximum subarray sum is
1 + 2 + 3 + 4 = 10.Constraints
- 1 <= nums.length <= 10^5
- -10^6 <= nums[i] <= 10^6