C++ 프로그램으로 크기 3 증가 부분 수열의 최대 곱 구하기

이 문제에서는 n개의 양의 정수로 구성된 배열 arr[]가 주어지며, 크기 3인 증가 부분 수열(increasing subsequence)의 최대 곱을 찾는 프로그램을 작성해야 합니다.

문제 설명

배열에서 3개의 원소를 골라 그 곱이 최대가 되도록 해야 하며, 세 원소는 값과 인덱스 모두 증가하는 순서를 이루어야 합니다. 즉, 다음 조건을 만족해야 합니다.

arr[i]*arr[j]*arr[k]가 최대,
arr[i]<arr[j]<arr[k]이고 i<j<k

예제로 이해하기

입력

arr = {5, 9, 2, 11, 4, 7}

출력

495

설명

조건을 만족하는 크기 3의 부분 배열은 다음과 같습니다.
(5, 9, 11) → 곱 = 5*9*11 = 495
(2, 4, 7) → 곱 = 2*4*7 = 56
따라서 최댓값은 495입니다.

접근 방식 1: 완전 탐색(Brute Force)

가장 간단한 방법은 배열을 삼중 반복문으로 순회하면서 조건(arr[i] < arr[j] < arr[k], i < j < k)을 만족하는 모든 크기 3의 부분 배열을 찾고, 각 경우의 곱을 계산한 뒤 그중 최댓값을 반환하는 것입니다.

알고리즘

초기화 −

maxProd = -1000

1단계 − i를 0부터 n−3까지 반복합니다.

1.1단계 − j를 i+1부터 n−2까지 반복합니다.

1.1.1단계 − arr[i] < arr[j]이면 k를 j+1부터 n−1까지 반복합니다.

1.1.1.1단계 − arr[j] < arr[k]이면 prod = arr[i]*arr[j]*arr[k]를 계산합니다.

1.1.1.2단계 − prod가 maxProd보다 크면 maxProd를 prod로 갱신합니다.

2단계 − maxProd를 반환합니다.

구현 예제

#include <iostream>
using namespace std;
int calcMaxProd(int arr[], int n){
    int maxProd = -1000;
    int prod;
    for (int i = 0; i < n - 2; i++)
    for (int j = i + 1; j < n - 1; j++)
    if(arr[i] < arr[j]){
        for (int k = j + 1; k < n; k++){
            if(arr[j] < arr[k]){
                prod = arr[i] * arr[j] * arr[k];
                if(maxProd < prod)
                    maxProd = prod;
            }
        }
    }
    return maxProd;
}
int main(){
    int arr[] = { 5, 9, 2, 11, 4, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"크기 3의 증가 부분 수열의 최대 곱은 "<<calcMaxProd(arr, n);
    return 0;
}

출력

크기 3의 증가 부분 수열의 최대 곱은 495

이 방법은 이해하기 쉽지만 3개의 중첩 반복문을 사용하므로 시간 복잡도가 O(n³)에 달합니다. 따라서 더 효율적인 풀이를 살펴보겠습니다.

접근 방식 2: 효율적인 풀이

효율적인 접근에서는 배열의 인덱스 1부터 n−2까지의 원소를 크기 3 부분 수열의 '가운데 원소'로 간주하고, 나머지 두 원소를 배열에서 찾습니다.

• 왼쪽 원소: 인덱스가 i보다 작으면서 값이 arr[i]보다 작은 원소 중 최댓값
• 오른쪽 원소: 인덱스가 i보다 크면서 값이 arr[i]보다 큰 원소 중 최댓값

왼쪽의 더 작은 원소는 자가 균형 이진 탐색 트리(self-balancing BST)를 이용해 찾고, 오른쪽의 더 큰 원소는 배열을 오른쪽에서 왼쪽으로 순회하며 추적합니다. 두 값을 찾으면 곱을 계산하고, 모든 경우를 비교하여 maxProd를 구합니다. 이 방법을 사용하면 시간 복잡도를 O(n log n)까지 줄일 수 있습니다.

구현 예제

#include<bits/stdc++.h>
using namespace std;
long calMaxSubSeqProd(int arr[] , int n) {
    int smallerLeftEle[n];
    smallerLeftEle[0] = -1 ;
    set<int>small ;
    for (int i = 0; i < n ; i++) {
        auto it = small.insert(arr[i]);
        auto val = it.first;
        --val;
        if (val != small.end())
        smallerLeftEle[i] = *val;
        else
        smallerLeftEle[i] = -1;
    }
    long maxProd = -10000;
    long prod ;
    int greaterRightEle = arr[n-1];
    for (int i= n-2 ; i >= 1; i--) {
        if (arr[i] > greaterRightEle)
            greaterRightEle = arr[i];
        else if (smallerLeftEle[i] != -1){
            prod = smallerLeftEle[i]*arr[i]*greaterRightEle;
            if(prod > maxProd)
                maxProd = prod;
        }
    }
    return maxProd;
}
int main() {
    int arr[] = {5, 9, 2, 11, 4, 7};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"크기 3의 증가 부분 수열의 최대 곱은 "<<calMaxSubSeqProd(arr, n);
    return 0;
}

출력

크기 3의 증가 부분 수열의 최대 곱은 495