LeetCode 筆記 - 1695. Maximum Erasure Value

Posted on

題目在此 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

完成 😆

相關文章