[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 S..
2022. 6. 12.
