Maximum Erasure Value
Medium · Sliding Window · Array · Hash Table · Sliding Window
Problem
You are given an array of positive integers nums. You may erase exactly one contiguous subarray whose elements are all different, and your score is the sum of the erased elements.
Return the largest score you can get.
Examples
Input: nums = [4,2,4,5,6] Output: 17
[2,4,5,6] has no repeats and sums to 17.
Input: nums = [3,3,3] Output: 3
Any window longer than one element repeats 3.
Input: nums = [5,2,1,2,5,2,1,2,5] Output: 8
[5,2,1] and [1,2,5] both sum to 8, the most possible.
Constraints
- 1 <= len(nums) <= 10^5
- 1 <= nums[i] <= 10^4
Approaches
- Baseline: extend from every start — time O(n · m), space O(m)
Follow-up
This is the longest repeat-free substring problem with sums instead of lengths, and it works because values are positive: a longer window is never worse. With negative values allowed, the best window for a right end is no longer the longest, and you would need prefix sums with the smallest prefix inside the allowed range.
Related problems
Start free on Cariara · Coding problems · System design studio
