LeetCode 筆記 - 1695. Maximum Erasure Value

題目在此 1695. Maximum Erasure Value

給你一個數列,請找到一個沒有重複元素並且總和最大的子數列

解題思維

這裡會用到 Sliding Window 的概念
再加上 Hash Map 來判斷是否有重複的元素

剩下就是使用了 Prefix Sum 來加速計算總和

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:

length = len(nums)
if length == 1:
return nums[0]

prefix_sum = collections.defaultdict(int)
for i in range(length):
prefix_sum[i] = prefix_sum[i - 1] + nums[i]

# num : index
seen = {}

result = 0
start = end = 0
for end in range(length):
if nums[end] in seen and start <= seen[nums[end]]:
start = seen[nums[end]] + 1
else:
current_sum = prefix_sum[end] - prefix_sum[start - 1]
result = max(result, current_sum)

seen[nums[end]] = end
end += 1

return result

完成 😆

也許你也會想看看