3410. Maximize Subarray Sum After Removing All Occurrences of One Element
Hard22.9% acceptance4,016 / 17,499 submissions
Asked by 2 companies
Topics
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: 7
Explanation:
We can have the following arrays after at most one operation:
- The original array is
nums = [-3, 2, -2, -1, 3, -2, 3]. The maximum subarray sum is3 + (-2) + 3 = 4. - Deleting all occurences of
x = -3results innums = [2, -2, -1, 3, -2, 3]. The maximum subarray sum is3 + (-2) + 3 = 4. - Deleting all occurences of
x = -2results innums = [-3, 2, -1, 3, 3]. The maximum subarray sum is2 + (-1) + 3 + 3 = 7. - Deleting all occurences of
x = -1results innums = [-3, 2, -2, 3, -2, 3]. The maximum subarray sum is3 + (-2) + 3 = 4. - Deleting all occurences of
x = 3results innums = [-3, 2, -2, -1, -2]. The maximum subarray sum is 2.
The output is max(4, 4, 7, 4, 2) = 7.
Example 2:
Input: nums = [1,2,3,4]
Output: 10
Explanation:
It is optimal to not perform any operations.
Constraints:
1 <= nums.length <= 105-106 <= nums[i] <= 106
Hints
Hint 1
Use a segment tree data structure to solve the problem.
Hint 2
Each node of the segment tree should store the subarray sum, the maximum subarray sum, the maximum prefix sum, and the maximum suffix sum within the subarray defined by that node.