1695.maximum-erasure-value.md

1695. Maximum Erasure Value

Sliding Window

The problem is actually asking to find "the subarray with maximum sum that has unique elements.".

It's a follow-up of the problem 3. Longest Substring Without Repeating Characters.

// Using set
fun maximumUniqueSubarray(nums: IntArray): Int {
    val set = HashSet<Int>()
    var sum = 0
    var max = 0
    var left = 0
    for (right in nums.indices) {
        // We check before adding right element to the set
        while (set.contains(nums[right])) {
            set.remove(nums[left])
            sum -= nums[left]
            left++
        }
        set.add(nums[right])
        sum += nums[right]
        max = maxOf(max, sum)
    }
    return max
}

// Or equivalently, it uses HashMap and follows the template I used in the sliding window
fun maximumUniqueSubarray(nums: IntArray): Int {
    val map = HashMap<Int, Int>()
    var sum = 0
    var left = 0
    var maxScore = 0
    for (right in nums.indices) {
        map[nums[right]] = (map[nums[right]] ?: 0) + 1
        sum += nums[right]
        while (map[nums[right]]!! > 1) {
            map[nums[left]] = map[nums[left]]!! - 1
            sum -= nums[left]
            left++
        }
        maxScore = maxOf(maxScore, sum)
    }
    return maxScore
}

WA

I was finding the longest unique element, which may not lead to maximum sum.

fun maximumUniqueSubarray(nums: IntArray): Int {
    val set = HashSet<Int>()
    var left = 0
    var maxScore = 0
    var l = 0
    var r = 0
    for (right in nums.indices) {
        while (set.contains(nums[right])) {
            set.remove(nums[left])
            left++
        }
        set.add(nums[right])
        if (right - left >= r - l) {
            l = left
            r = right
        }
    }
    for (i in l..r) {
        maxScore += nums[i]
    }
    return maxScore
}