Maximum Erasure Value — LeetCode 1695 Python Solution

The problem

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Example

Input

nums = [4,2,4,5,6]

Output

17

Explanation

The optimal subarray here is [2,4,5,6].

Python solution

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        d = [0] * (max(nums) + 1)
        s = list(accumulate(nums, initial=0))
        ans = j = 0
        for i, v in enumerate(nums, 1):
            j = max(j, d[v])
            ans = max(ans, s[i] - s[j])
            d[v] = i
        return ans

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1695. Maximum Erasure Value is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems