숫자로 이루어진 리스트 nums가 주어졌을 때, 값이 엄격하게 증가하는 부분 수열을 선택하는 문제를 생각해 보겠습니다. 여기서 중요한 조건은 인접한 두 숫자의 값 차이가 반드시 해당 인덱스의 차이와 같아야 한다는 점입니다. 우리의 목표는 이러한 조건을 만족하는 부분 수열 중 합이 최대가 되는 것을 찾는 것입니다.
예를 들어 입력이 nums = [6, 7, 9, 9, 8, 5]라고 한다면, 정답은 22입니다. 인덱스 [0, 1, 3]에 위치한 부분 수열 [6, 7, 9]를 선택하면, 연속된 값들의 차이는 [1, 2]이고 이는 인덱스 차이 [1, 2]와 정확히 일치하기 때문입니다.
핵심 아이디어
이 문제를 효율적으로 풀기 위한 핵심 관찰은 다음과 같습니다. 두 원소의 값 차이가 인덱스 차이와 같다는 조건(x₂ − x₁ = i₂ − i₁)은 양변을 정리하면 x₁ − i₁ = x₂ − i₂, 즉 (값 − 인덱스)가 모든 선택된 원소에서 동일하다는 의미입니다.
따라서 각 원소를 '값에서 인덱스를 뺀 값'을 키(key)로 하는 그룹에 묶고, 그룹별로 원소 값의 합을 누적한 뒤 그중 가장 큰 값을 반환하면 됩니다. 같은 그룹에 속한 원소들은 자동으로 값 차이와 인덱스 차이가 일치하는 부분 수열을 형성합니다.
알고리즘 단계
d := 빈 딕셔너리(맵)를 생성합니다.
nums의 각 인덱스 i와 값 x에 대해 다음을 수행합니다:
d[x − i] := d[x − i] + xd의 모든 값 중 최대값을 반환합니다.
이 알고리즘의 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)으로 매우 효율적입니다.
구현 예제
class Solution: def solve(self, nums): from collections import defaultdict d = defaultdict(int) for i, x in enumerate(nums): d[x − i] += x return max(d.values()) ob1 = Solution() nums = [6, 7, 9, 9, 8, 5] print(ob1.solve(nums))
입력
[6, 7, 9, 9, 8, 5]
출력
22
위 코드에서 defaultdict(int)를 사용하면 존재하지 않는 키에 접근할 때 자동으로 0으로 초기화되므로, 키 존재 여부를 따로 확인하지 않고도 깔끔하게 누적 합계를 계산할 수 있습니다. 마지막으로 max(d.values())를 호출하여 그룹별 합계 중 가장 큰 값을 반환함으로써 문제의 답을 얻게 됩니다.