[Algorithm] Sliding Window + 1695. Maximum Erasure Value

array에서 특정 구간의 최대 합을 찾을 때, 인덱스 0부터 모든 subarray의 합을 구해볼 수 있을 것이다.

이 때 시간복잡도는 O(n^2)으로, Sliding Window기법을 통해 시간복잡도를 O(n)으로 낮출 수 있다.

 

리트코드 1695. Maximum Erasure Value

= unique한 값만 존재하는 subarray의 합 중 가장 큰 합 찾기

[4, 2, 1, 2, 6]

1. 인덱스 0부터 윈도우 크기를 키우다가, 중복되는 값이 나오면 (=2) 앞에서부터 윈도우 크기를 줄임

[4] = 4

[4, 2] = 6

[4, 2, 1] = 7

[2, 1, 2]

[1, 2]

2. 윈도우에 unique한 값만 존재하면, 합이 얼마인지 찾기

[1, 2] = 3

[1, 2, 6] = 9

class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        seen = set()
        curr_sum, max_sum, l = 0, 0, 0
        
        for num in nums:
            while num in seen:
                curr_sum -= nums[l]
                seen.remove(nums[l])
                l += 1
                
            curr_sum += num
            seen.add(num)
            
            max_sum = max(max_sum, curr_sum)

        return max_sum

 

왼쪽은 브루트포스로 모든 subarray를 탐색하는 방법, 오른쪽이 Sliding Window로 찾았을 때의 그림이다.

 

https://leetcode.com/problems/maximum-erasure-value/discuss/2140750/C%2B%2BPython-Simple-Solution-w-Explanation-or-Sliding-Window

https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples