C++로 i < j < k이면서 a[i] < a[j] < a[k]인 삼중항의 최대 합 구하기

개념

크기가 n인 양의 정수 배열이 주어졌을 때, 인덱스 조건 0 <= i < j < k < n과 값 조건 a_i < a_j < a_k를 동시에 만족하는 삼중항( a_i + a_j + a_k )의 최대 합을 구하는 것이 이번 문제의 목표입니다.

입력

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

풀이 방법

단순한 접근법은 세 개의 중첩 'for 루프'로 가능한 모든 삼중항을 하나씩 확인하면서 합을 갱신하는 방식입니다. 다만 이 방법의 시간 복잡도는 O(n³)이므로 n이 커질수록 성능이 급격히 저하되어 실용성이 떨어집니다.

더 나은 접근법을 적용하면 위 방식을 한 단계 더 최적화할 수 있습니다. 이 방법에서는 세 개의 중첩 루프 대신 두 개의 중첩 루프만 사용하며, 시간 복잡도를 O(n²)까지 줄일 수 있습니다.

배열의 각 원소를 중간 원소(a_j)로 가정하고 순회하면서, 해당 원소 앞쪽 구간에서 a_j보다 작은 값들 중 최댓값(a_i)을 찾고, 뒤쪽 구간에서 a_j보다 큰 값들 중 최댓값(a_k)을 찾습니다. 그런 다음 계산된 a_i + a_j + a_k의 합으로 지금까지의 최대 답을 갱신하면 됩니다.

예제 코드

// C++ 프로그램: 최대 삼중항 합 찾기
#include <bits/stdc++.h>
using namespace std;

// 최대 삼중항 합을 계산하는 함수
int maxTripletSum(int arr1[], int n1){
    // 정답 변수 초기화
    int ans1 = 0;
    // 각 원소를 중간 원소로 가정하고 순회
    for (int i = 1; i < n1 - 1; ++i) {
        int max1 = 0, max2 = 0;
        // arr1[i]보다 작은 값 중 최댓값 탐색 (인덱스 0 ~ i-1)
        for (int j = 0; j < i; ++j)
            if (arr1[j] < arr1[i])
                max1 = max(max1, arr1[j]);
        // arr1[i]보다 큰 값 중 최댓값 탐색 (인덱스 i+1 ~ n1-1)
        for (int j = i + 1; j < n1; ++j)
            if (arr1[j] > arr1[i])
                max2 = max(max2, arr1[j]);
        // 좌우 조건을 모두 만족하는 경우에만 최대 답 갱신
        if(max1 && max2)
            ans1 = max(ans1, max1 + arr1[i] + max2);
    }
    return ans1;
}

// 메인 함수
int main(){
    int Arr[] = { 3, 6, 4, 2, 5, 10 };
    int N = sizeof(Arr) / sizeof(Arr[0]);
    cout << maxTripletSum(Arr, N);
    return 0;
}

실행 결과

정리

이 알고리즘은 각 원소를 중간 값으로 고정한 뒤 좌측에서는 더 작은 값의 최댓값을, 우측에서는 더 큰 값의 최댓값을 탐색하기 때문에 완전탐색(O(n³))보다 훨씬 효율적으로 동작합니다. 조건을 만족하는 좌측·우측 후보가 존재하지 않는 경우에는 해당 원소를 건너뛰도록 처리했으므로, 오름차순 삼중항이 전혀 없는 배열에서도 안전하게 0을 반환합니다.