C++ 동적 계획법으로 증가 부분 수열의 최대 곱 구하기

문제 소개

이 글에서는 정수 배열이 주어졌을 때 증가하는 부분 수열(increasing subsequence)의 원소들을 곱하여 얻을 수 있는 최댓값을 구하는 프로그램을 C++로 작성해 보겠습니다.

여기서 부분 수열(subsequence)이란 배열에서 원소들의 상대적인 순서를 유지한 채 일부 원소를 선택한 것을 의미합니다. 단, 선택된 원소들은 반드시 왼쪽에서 오른쪽으로 값이 커져야 하며, 부분 수열의 길이에는 제한이 없습니다.

예시로 이해하기

배열이 {3, 100, 4, 5, 150, 6}라고 가정해 봅시다. 이 배열에서 만들 수 있는 증가 부분 수열 중 하나는 3, 100, 150입니다. 이 수열의 곱은 3 × 100 × 150 = 45,000이며, 가능한 모든 조합을 비교해 보아도 이 값이 가장 큽니다. 따라서 정답은 45000입니다.

풀이 접근: 동적 계획법(Dynamic Programming)

이 문제는 잘 알려진 LIS(최장 증가 부분 수열) 알고리즘과 거의 같은 구조를 가지고 있습니다. 핵심 아이디어는 다음과 같습니다.

상태 정의: mpis[i] = 인덱스 i의 원소로 끝나는 증가 부분 수열의 최대 곱
초기값: mpis[i] = arr[i] — 자기 자신 하나만으로 이루어진 부분 수열
점화식: j < i이면서 arr[i] > arr[j]인 모든 j에 대해 mpis[i] = max(mpis[i], mpis[j] × arr[i])
최종 답: mpis 배열 전체 요소 중 최댓값

C++ 구현 코드

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

// 증가 부분 수열의 최대 곱을 반환하는 함수
ll lis(ll arr[], ll n) {
    ll mpis[n];
    // 초기값 설정: 각 원소 자신으로 초기화
    for (int i = 0; i < n; i++)
        mpis[i] = arr[i];
    // 동적 계획법으로 최대 곱 갱신
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (arr[i] > arr[j] && mpis[i] < (mpis[j] * arr[i]))
                mpis[i] = mpis[j] * arr[i];
    // mpis 배열 전체에서 최댓값 반환
    return *max_element(mpis, mpis + n);
}

int main() {
    ll arr[] = { 3, 100, 4, 5, 150, 6 };
    ll n = sizeof(arr) / sizeof(arr[0]);
    printf("%lld", lis(arr, n));
    return 0;
}

실행 결과

단계별 동작 과정

입력 배열 {3, 100, 4, 5, 150, 6}에 대해 DP 테이블이 채워지는 과정은 다음과 같습니다.

mpis[0] = 3 — 시작 원소
mpis[1] = 3 × 100 = 300
mpis[2] = 3 × 4 = 12
mpis[3] = 12 × 5 = 60
mpis[4] = 300 × 150 = 45000 ← 최댓값
mpis[5] = 60 × 6 = 360

배열 전체에서 가장 큰 값인 45000이 최종 결과가 됩니다.

복잡도 분석

시간 복잡도: O(n²) — 각 원소마다 앞선 모든 원소와 비교
공간 복잡도: O(n) — DP 테이블 저장 공간

n이 매우 큰 경우 세그먼트 트리 등을 활용하면 더 빠르게 최적화할 수 있지만, 대부분의 경우 위의 O(n²) 동적 계획법 풀이로 충분합니다.