1695. Maximum Erasure Value

Problem

Tags: Array, Hash Table, Sliding Window

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].

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4

Code

GO

// 1695. Maximum Erasure Value (1/23/53376)
// Runtime: 192 ms (65.22%) Memory: 8.64 MB (86.96%) 

func maximumUniqueSubarray(nums []int) int {
    max, sum := 0, 0
	table := make(map[int]int)

	front, back := 0, 0
	for front = 0; front < len(nums); front++ {
        sum += nums[front]
		if pos, exists := table[nums[front]]; exists {
			for back <= pos {
				delete(table, nums[back])
                sum -= nums[back]
				back++
			}
		} else if sum > max {
			max = sum
		}
		table[nums[front]] = front
	}

	return max
}

JS

// 1695. Maximum Erasure Value (1/18/53376)
// Runtime: 148 ms (87.33%) Memory: 53.86 MB (90.14%) 

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumUniqueSubarray = function(nums) {
    // 暫存最大總和
    let max = 0;
    // hash table
    let table = {};
    // 子陣列當前總和
    let sum = 0;
    
    // 子陣列頭尾位置
    let front = 0, back = 0;
    for(front = 0; front < nums.length; front++) {
        sum += nums[front];
        if(table[nums[front]] !== undefined) {
            // 如果有紀錄，尾端前推至該紀錄位置的下個位置
            while(back <= table[nums[front]]) {
                table[nums[back]] = undefined;
                sum -= nums[back];
                back++;
            }
        } else {
            // 試圖更新最大總和
            max = sum > max ? sum : max;
        }
        table[nums[front]] = front;
    }
    
    return max;
};