max_eraser_value.go

/*
    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.

    Return the maximum score you can get by erasing exactly one subarray.

    An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

    

    Example 1:

    Input: nums = [4,2,4,5,6]
    Output: 17
    Explanation: The optimal subarray here is [2,4,5,6].
    Example 2:

    Input: nums = [5,2,1,2,5,2,1,2,5]
    Output: 8
    Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

    Explanation:

    startWindow: The left end of the sliding window.
    windowSum: Sum of elements within the current window.
    res: Result, initialized to 0, representing the maximum unique subarray sum.
    mp: HashMap to store the last index where each element was seen.
    Sliding Window:

    Use a for loop to iterate through the array with the endWindow as the right end of the window.
    Check if the current element is already in the window using a while loop.
    If yes, remove the element at the start of the window from the HashMap and update windowSum and startWindow.
    Update HashMap and windowSum:

    Add the current element to the HashMap and update windowSum.
    Update Result:

    Update the result (res) with the maximum unique subarray sum.
    Return Result:

    Return the final result, which represents the maximum unique subarray sum.
    This code efficiently finds the maximum sum of a subarray where all elements are unique using a sliding window and a HashMap to keep track of the last index of each element encountered.

*/
package main

import "fmt"

func maximumUniqueSubarray(nums []int) int {
    startWindow := 0          // The left end of the sliding window
    windowSum := 0            // Sum of elements within the current window
    res := 0                  // Result, which represents the maximum unique subarray sum
    mp := make(map[int]int)   // Map to store the last index where each element was seen

    // Iterate through the array using a sliding window approach
    for endWindow := 0; endWindow < len(nums); endWindow++ {
        // Check if the current element is already in the window
        for mp[nums[endWindow]] > 0 {
            // Remove the element at the start of the window from the map and update windowSum
            mp[nums[startWindow]]--
            windowSum -= nums[startWindow]
            startWindow++
        }

        // Add the current element to the map and update windowSum
        mp[nums[endWindow]]++
        windowSum += nums[endWindow]

        // Update the result with the maximum unique subarray sum
        if windowSum > res {
            res = windowSum
        }
    }

    // Return the result, which represents the maximum unique subarray sum
    return res
}

func main() {
    nums := []int{4, 2, 4, 5, 6}
    result := maximumUniqueSubarray(nums)
    fmt.Println(result) // Output: 17
}