C++로 증가 부분 수열의 최대 곱 구하기

문제 개요

이 문제에서는 크기가 n인 배열 arr[]가 주어지며, 우리의 과제는 증가 부분 수열(increasing subsequence)의 곱 중 최댓값을 찾는 것입니다.

문제 설명 — 배열의 원소들로 만들 수 있는 모든 길이의 증가 부분 수열 중에서, 원소들의 곱이 가장 커지는 경우의 값을 구해야 합니다.

예제로 문제 이해하기

입력

arr[] = {5, 4, 6, 8, 7, 9}

출력

설명

가능한 증가 부분 수열:
{5, 6, 8, 9} → 곱 = 2160
{5, 6, 7, 9} → 곱 = 1890
여기서는 최대 길이의 부분 수열만 고려했습니다.

위 예제에서 정답은 {5, 6, 8, 9}를 선택했을 때 얻는 2160입니다.

풀이 접근 방법

이 문제를 효율적으로 해결하는 방법은 동적 계획법(Dynamic Programming)을 활용하는 것입니다. 배열의 각 위치까지 살펴봤을 때 만들 수 있는 증가 부분 수열의 최대 곱을 별도의 배열에 저장하고, 이전 결과를 재활용하며 값을 갱신해 나갑니다.

핵심 아이디어는 다음과 같습니다. 어떤 원소 arr[i]가 그보다 앞의 원소 arr[j]보다 클 때(즉, 증가 관계를 만족할 때), prod[j]에 arr[i]를 곱한 값이 현재 prod[i]보다 크다면 prod[i]를 갱신합니다.

알고리즘

초기화

prod[] 배열을 arr[]의 원소 값으로 초기화
maxProd = -1000

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

1.1단계 — j를 0부터 i-1까지 반복합니다.

1.1.1단계 — 현재 원소가 증가 부분 수열을 이루는지 확인합니다. 즉, arr[i] > arr[j]이면서 arr[i] * prod[j] > prod[i]라면 prod[i] = prod[j] * arr[i]로 갱신합니다.

2단계 — 배열 전체에서 최댓값을 찾습니다. 아래 3~4단계를 수행합니다.

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

4단계 — prod[i] > maxProd이면 maxProd = prod[i]로 갱신합니다.

5단계 — maxProd를 반환합니다.

구현 예제

다음은 위 풀이를 실제로 구현한 C++ 프로그램입니다.

#include <iostream>
using namespace std;
long calcMaxProdSubSeq(long arr[], int n) {
    long maxProdSubSeq[n];
    for (int i = 0; i < n; i++)
    maxProdSubSeq[i] = arr[i];
    for (int i = 1; i < n; i++)
    for (int j = 0; j < i; j++)
    if (arr[i] > arr[j] && maxProdSubSeq[i] <
       (maxProdSubSeq[j] * arr[i]))
    maxProdSubSeq[i] = maxProdSubSeq[j] * arr[i];
    long maxProd = −1000 ;
    for(int i = 0; i < n; i++){
       if(maxProd < maxProdSubSeq[i])
          maxProd = maxProdSubSeq[i];
    }
    return maxProd;
}
int main() {
    long arr[] = {5, 4, 6, 8, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum product of an increasing subsequence is "<<calcMaxProdSubSeq(arr, n);
    return 0;
}

출력

The maximum product of an increasing subsequence is 2160

복잡도 분석

위 풀이는 두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, 최대 곱을 저장하기 위한 추가 배열 하나만 필요하므로 공간 복잡도는 O(n)입니다. 원소의 개수가 수천 수준이라면 충분히 빠르게 동작하는 실용적인 접근 방식입니다.