문제 개요
n개의 정수로 이루어진 배열 nums가 있다고 가정해 보겠습니다. 배열의 각 값은 해당 요소 고유의 '파워(power)'를 나타냅니다. 이 배열은 아래 두 조건을 동시에 만족할 때 '유효(valid)하다'고 정의합니다.
- 배열의 길이가 2보다 커야 합니다.
- 배열의 첫 번째 값과 마지막 값이 서로 같아야 합니다.
우리는 배열에서 요소를 삭제하여 이 조건을 만족하는 유효한 배열을 만들어야 하며, 그 결과 남은 요소들의 파워 값을 모두 더했을 때 얻을 수 있는 최댓값을 반환해야 합니다.
예를 들어 입력이 nums = [3, 4, 5, 3, 4]라면 출력은 16입니다. 배열에서 첫 번째 값 3을 제거하면 [4, 5, 3, 4]가 되는데, 이 배열은 첫 값과 마지막 값이 4로 같으므로 유효합니다. 이때 파워의 합은 4 + 5 + 3 + 4 = 16이며, 주어진 입력으로 만들 수 있는 유효한 배열 중 가장 큰 합입니다.
해결 접근 방법
핵심 아이디어는 각 값이 처음 등장한 위치와 마지막에 등장한 위치 사이의 구간을 후보로 삼고, 누적 합(prefix sum)을 활용해 구간합을 빠르게 계산하는 것입니다. 또한 구간 내부에 있는 음수 요소는 제거하면 합이 커지므로, 이를 별도의 누적 리스트로 관리해 차감합니다. 구체적인 단계는 다음과 같습니다.
table := 새로운 맵(딕셔너리)을 생성합니다.
prefix := 0으로 초기화된 새로운 리스트를 만듭니다. (전체 누적 합 저장)
negative := 0으로 초기화된 새로운 리스트를 만듭니다. (음수 누적 합 저장)
nums의 각 인덱스 i와 값 j에 대해 다음을 반복합니다.
- j가 table에 없으면 table[j] := 새로운 쌍 (i, 0)을 저장합니다.
- 이미 존재한다면 table[j][-1] := i로 갱신해 마지막 등장 위치를 기록합니다.
- prefix의 마지막 원소에 j를 더한 값을 새 원소로 추가합니다.
- negative의 마지막 원소를 그대로 복제해 추가합니다.
- 만약 j < 0이라면 negative의 마지막 원소에 j를 더합니다.
ans := 음의 무한대(-∞)로 초기화합니다.
table의 모든 값 쌍 (i, j)에 대해 다음을 수행합니다.
- j가 0이 아니라면(해당 값이 두 번 이상 등장했다면):
- sm1 := prefix[j+1] − prefix[i] → 첫 등장 위치부터 마지막 등장 위치까지의 구간 합
- j > i+1이면 sm2 := negative[j] − negative[i+1] → 구간 내부 음수들의 합, 아니면 sm2 := 0
- ans := ans와 (sm1 − sm2) 중 더 큰 값으로 갱신합니다.
ans를 반환합니다.
예시 구현
아래 파이썬 코드를 통해 동작 과정을 더 자세히 살펴보겠습니다.
def solve(nums):
table = {}
prefix = [0]
negative = [0]
for i, j in enumerate(nums):
if j not in table:
table[j] = [i, 0]
else:
table[j][-1] = i
prefix += prefix[-1] + j,
negative += negative[-1],
if j < 0:
negative[-1] += j
ans = float('-inf')
for i,j in table.values():
if j != 0:
sm1 = prefix[j+1] - prefix[i]
sm2 = negative[j] - negative[i+1] if j > i+1 else 0
ans = max(ans, sm1 - sm2)
return ans
print(solve([3, 4, 5, 3, 4]))
입력
[3, 4, 5, 3, 4]
출력
16
동작 원리 정리
이 알고리즘은 세 가지 장치를 조합해 효율적으로 답을 구합니다.
- table: 각 값이 처음 등장한 인덱스와 마지막에 등장한 인덱스를 함께 저장해, 유효한 배열의 시작점과 끝점 후보를 즉시 파악합니다.
- prefix: 누적 합 배열을 이용해 임의 구간의 합을 상수 시간(O(1))에 계산합니다.
- negative: 구간 내부의 음수만 모아 둔 누적 합으로, 내부 음수를 제거했을 때 얻는 이득을 한 번의 뺄셈으로 반영합니다.
덕분에 전체 시간 복잡도는 선형(O(n)) 수준으로 유지되며, 배열이 매우 길어도 빠르게 최댓값을 찾을 수 있습니다.