1695. Maximum Erasure Value
給一個正整數矩陣nums
想要找到一個subarray該subarray所包含的元素都是唯一的
nums會包含一個或多個這種subarray
請回傳所有元素相加後總和最大的subarray
思路:
標準的two pointer題目
就一路從頭加到尾(sum)
用hash table記錄每一個數字出前一次出現的index
當遇到重複的數字時
先比較目前的最大值和sum誰比較大
接著從左指標開始從sum扣掉直到該數字前一次出現的位置
中間記得把hash table裡每個數字前一次出現的位置更新
這樣應該就可以得到答案了
golang code :
func maximumUniqueSubarray(nums []int) int {
rec := make(map[int]int)
first_idx, n, ans, sum := 0, len(nums), 0, 0
for i := 0; i < n; i++ {
if rec[nums[i]] == 0 {
sum += nums[i]
rec[nums[i]] = i + 1
} else {
ans = max(ans, sum)
tmp := rec[nums[i]]
for first_idx != tmp {
sum -= nums[first_idx]
rec[nums[first_idx]] = 0
first_idx++
}
i