Python으로 i < j < k와 a[i] < a[j] < a[k] 조건을 만족하는 삼중항의 최대 합 찾기

문제 개요

양수로만 이루어진 배열이 주어져 있다고 가정해 봅시다. 배열에는 n개의 요소가 있으며, 우리는 다음 두 조건을 동시에 만족하는 삼중항(ai + aj + ak)의 최대 합을 구해야 합니다.

조건: 0 <= i < j < k < n 이면서 ai < aj < ak

즉, 세 요소의 인덱스 순서와 값의 크기 순서가 모두 오름차순을 유지해야 한다는 의미입니다.

입력 예시

배열 A = [3, 6, 4, 2, 5, 10]이 주어졌을 때, 가능한 삼중항과 각각의 합은 다음과 같습니다.

(3, 4, 5): 합 = 12
(3, 6, 10): 합 = 19
(3, 4, 10): 합 = 17
(4, 5, 10): 합 = 19
(2, 5, 10): 합 = 17

따라서 최대 합은 19가 됩니다.

해결 접근 방법

이 문제는 각 요소를 '가운데 값'으로 고정하고, 왼쪽에서는 자신보다 작은 값의 최댓값을, 오른쪽에서는 자신보다 큰 값의 최댓값을 찾는 방식으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.

n := 배열 A의 크기로 설정합니다.
res := 0으로 초기화합니다. (결과값 저장용)
i를 1부터 n - 2까지 반복하며 A[i]를 가운데 값으로 지정합니다.
- first_max := 0, second_max := 0으로 초기화합니다.
- j를 0부터 i - 1까지 반복하며, A[j] < A[i]인 경우 first_max를 first_max와 A[j] 중 더 큰 값으로 갱신합니다.
- j를 i + 1부터 n - 1까지 반복하며, A[j] > A[i]인 경우 second_max를 second_max와 A[j] 중 더 큰 값으로 갱신합니다.
- first_max와 second_max가 모두 0이 아니라면(즉, 유효한 좌우 값이 존재한다면) res를 res와 first_max + A[i] + second_max 중 더 큰 값으로 갱신합니다.
모든 반복이 끝나면 res를 반환합니다.

구현 예제

다음 Python 코드를 통해 위 알고리즘을 더 잘 이해할 수 있습니다.

def get_max_triplet_sum(A):
    n = len(A)
    res = 0
    # A[i]를 가운데 값으로 고정
    for i in range(1, n - 1):
        first_max = 0   # 왼쪽에서 A[i]보다 작은 값의 최댓값
        second_max = 0  # 오른쪽에서 A[i]보다 큰 값의 최댓값
        # 왼쪽 부분 탐색
        for j in range(0, i):
            if A[j] < A[i]:
                first_max = max(first_max, A[j])
        # 오른쪽 부분 탐색
        for j in range(i + 1, n):
            if A[j] > A[i]:
                second_max = max(second_max, A[j])
        # 유효한 삼중항이 존재하면 결과 갱신
        if first_max and second_max:
            res = max(res, first_max + A[i] + second_max)
    return res

A = [3, 6, 4, 2, 5, 10]
print(get_max_triplet_sum(A))

실행 결과

[3, 6, 4, 2, 5, 10]

복잡도 분석

이 알고리즘은 각 가운데 인덱스마다 왼쪽과 오른쪽을 각각 한 번씩 탐색하므로 시간 복잡도는 O(n²)입니다. 추가적인 배열을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 만약 더 큰 입력에 대해 O(n log n) 또는 O(n) 성능이 필요하다면, 왼쪽 최댓값과 오른쪽 최댓값을 미리 계산해 두는 접두사/접미사 배열 방식을 활용할 수 있습니다.