C++에서 부분 배열의 모든 요소에 X를 곱한 후 최대 부분 배열 합 구하기

이 문제에서는 정수 배열과 정수 변수 'X'가 주어집니다. 먼저 주어진 배열에서 부분 배열(subarray)을 선택한 뒤, 해당 부분 배열의 모든 요소에 정수 X를 곱합니다. 그 후 전체 배열에서 만들 수 있는 최대 부분 배열 합을 구하는 것이 과제입니다.

입출력 예시

다양한 입력 및 출력 시나리오를 살펴보겠습니다.

예시 1

입력 − int arr[] = {2, 4, 1, -5, -2}, X = 3

출력 − 부분 배열의 모든 요소에 X를 곱한 후의 최대 부분 배열 합: 21

설명 − 배열과 정수 X가 주어졌습니다. 먼저 배열에서 부분 배열 {2, 4, 1}을 선택하고, 해당 부분 배열의 모든 요소에 X(즉, 3)를 곱하면 배열은 {6, 12, 3, -5, -2}가 됩니다. 마지막으로 최대 부분 배열 합을 계산하면 6 + 12 + 3 = 21이 됩니다.

예시 2

입력 − int arr[] = {-1, 2, -6, 3, -4}, X = -1

출력 − 부분 배열의 모든 요소에 X를 곱한 후의 최대 부분 배열 합: 11

설명 − 배열과 정수 X(-1)가 주어졌습니다. 음수인 X를 활용하기 위해 부분 배열 {-1, -6, -4}를 선택하고, 각 요소에 -1을 곱하면 배열은 {1, 2, 6, 3, 4}가 됩니다. 이때 최대 부분 배열 합은 1 + 6 + 4 = 11입니다.

프로그램에 사용된 접근 방식

정수 배열과 정수 변수 'X'를 입력받습니다. 배열의 크기를 계산한 후 Max_Subarray(arr, size, x) 함수에 데이터를 전달합니다.
Max_Subarray(arr, size, x) 함수 내부:
- int형 2차원 배열 arr_2[size][3]을 선언하고 임시 변수 temp를 0으로 초기화합니다.
- C++의 memset() 메서드를 사용하여 배열 'arr_2'의 모든 요소를 -1로 초기화합니다.
- i가 0부터 배열 크기까지 반복하는 FOR 루프를 시작합니다. 루프 안에서 temp를 max(temp, check(i, 0, arr, arr_2, size, x)) 호출 결과로 설정합니다.
- temp를 반환합니다.
check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x) 함수 내부:
- 임시 변수 count를 0으로 선언합니다.
- first == size이면 0을 반환합니다.
- arr_2[first][last] != -1이면 arr_2[first][last] 값을 반환합니다(메모이제이션).
- last == 0이면 C++의 내장 max 함수를 호출하여 count = max(count, arr[first] + check(first + 1, 0, ...))를 계산하고, 또한 count = max(count, x * arr[first] + check(first + 1, 1, ...))로 설정합니다. 즉, 현재 요소를 그대로 더하거나 X를 곱해 더하는 두 가지 경우를 비교합니다.
- 그렇지 않고 last == 1이면(이미 X를 곱한 상태) count = max(count, x * arr[first] + check(first + 1, 1, ...))와 count = max(count, arr[first] + check(first + 1, 2, ...))로 설정합니다. 즉, 곱셈 상태를 유지하거나 종료할 수 있습니다.
- 그 외의 경우(last == 2, 곱셈 종료 상태)에는 count = max(count, arr[first] + check(first + 1, 2, ...))만 계산합니다.
- 결과를 arr_2[first][last]에 저장하고 반환합니다.
최종 결과를 출력합니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;
#define Max_size 5

int check(int first, int last, int arr[], int arr_2[Max_size][3], int size, int x){
    int count = 0;
    if(first == size){
        return 0;
    }
    if(arr_2[first][last] != -1){
        return arr_2[first][last];
    }
    if (last == 0){
        count = max(count, arr[first] + check(first + 1, 0, arr, arr_2, size, x));
        count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
    }
    else if(last == 1){
        count = max(count, x * arr[first] + check(first + 1, 1, arr, arr_2, size, x));
        count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
    }
    else{
        count = max(count, arr[first] + check(first + 1, 2, arr, arr_2, size, x));
    }
    return arr_2[first][last] = count;
}

int Max_Subarray(int arr[], int size, int x){
    int arr_2[size][3];
    int temp = 0;
    memset(arr_2, -1, sizeof arr_2);
    for(int i = 0; i < size; i++){
        temp = max(temp, check(i, 0, arr, arr_2, size, x));
    }
    return temp;
}

int main(){
    int arr[] = {2, 4, 1, -5, -2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    cout<<"Maximize the subarray sum after multiplying all elements of any subarray with X are: "<<Max_Subarray(arr, size, x);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Maximize the subarray sum after multiplying all elements of any subarray with X are: 21

이 알고리즘은 재귀 호출과 메모이제이션(memoization)을 결합한 동적 계획법(DP) 기반 접근 방식입니다. last 매개변수는 현재 위치에서 X 곱셈 연산의 상태(0: 아직 시작하지 않음, 1: 진행 중, 2: 종료됨)를 추적하여, 각 요소에 대해 곱셈을 적용할지 여부를 최적으로 결정할 수 있게 해줍니다.