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