C++에서 주어진 배열을 k번 반복하여 형성된 배열의 최대 부분배열 합 구하기

이 문제에서는 하나의 배열과 정수 k가 주어지며, 주어진 배열을 k번 반복하여 만든 새로운 배열에서 최대 부분배열 합(maximum subarray sum)을 찾는 프로그램을 C++로 작성해야 합니다.

문제 설명

주어진 배열을 k번 이어 붙여 형성된 배열에서 얻을 수 있는 연속된 부분배열 중, 원소들의 합이 가장 큰 부분배열의 합을 구하는 것이 목표입니다.

예제를 통해 문제를 살펴보겠습니다.

입력 − array = {3, 5, 1}, k = 2

출력 − 18

설명 −

배열을 k번 반복하여 형성된 배열,
array = {3, 5, 1, 3, 5, 1}
최대 부분배열 합 = 3 + 5 + 1 + 3 + 5 + 1 = 18

풀이 접근 방법

이 문제를 효율적으로 해결하려면, 실제로 배열을 k번 모두 복사하지 않고 원래 배열의 정보만으로 답을 구해야 합니다. 핵심 아이디어는 다음과 같습니다.

먼저 배열의 모든 원소의 합(arraySum)을 계산한 뒤, 그 값의 부호에 따라 처리 방식을 나눕니다.

arraySum > 0인 경우 : 배열 전체의 합이 양수이므로 반복 횟수가 늘어날수록 부분배열 합이 커질 수 있습니다. 따라서 배열을 두 번 반복한 배열에서 최대 부분배열 합을 구하고, 여기에 (k − 2) × arraySum을 더해 최종 결과를 얻습니다.
arraySum ≤ 0인 경우 : 배열 전체를 포함해도 합이 증가하지 않으므로, 배열을 두 번 반복한 배열에서 구한 최대 부분배열 합을 그대로 사용합니다.

배열을 정확히 두 번 반복해서 검사하는 이유는, 한 번의 복사본만으로는 첫 번째 복사본의 뒷부분과 두 번째 복사본의 앞부분이 이어지는 경계 지점의 부분배열을 확인할 수 없기 때문입니다. 최적의 부분배열은 최대 두 개의 인접한 복사본에 걸칠 수 있으므로 두 번의 반복이면 충분합니다.

최대 부분배열 합 자체는 카데인 알고리즘(Kadane's algorithm)을 사용하면 선형 시간에 구할 수 있습니다.

구현 예제

위에서 설명한 풀이를 구현한 C++ 프로그램은 다음과 같습니다.

#include<iostream>
using namespace std;
void repeatArray(int *arr, int *b, int k,int len) {
    int j = 0;
    while (k > 0){
        for (int i = 0; i < len; i++)
        b[j++] = arr[i];
        k--;
    }
}
long subArraySum(int *a,int len) {
    int max = 0;
    long newmax = 0;
    for (int i = 0; i < len; i++) {
        newmax = newmax + a[i];
        if (max < newmax)
            max = newmax;
        if (newmax < 0)
            newmax = 0;
    }
    return max;
}
long findMaxSubArraySum(int *arr, int k,int len) {
    int arraySum = 0;
    long maxSum = 0;
    int b[(2 * len)]= {0};
    repeatArray(arr, b, 2,len);
    for (int i = 0; i < len; i++)
        arraySum += arr[i];
    maxSum = subArraySum(b,2*len);
    if (arraySum > 0)
        maxSum = subArraySum(b,2*len) + (k - 2) * arraySum;
    return maxSum;
}
int main() {
    int arr[] = { 3, 5, 1};
    int length=sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout<<"The maximum subarray sum in array formed by repeating the given array "<<k<<" times is "<<findMaxSubArraySum(arr, k,length);
    return 0;
}

실행 결과

The maximum subarray sum in array formed by repeating the given array 3 times is 27

복잡도 분석

시간 복잡도는 길이 2n짜리 배열에 대해 카데인 알고리즘을 한 번 수행하므로 O(n)입니다. 공간 복잡도 역시 두 배 길이의 임시 배열을 사용하므로 O(n)입니다. 이처럼 배열을 k번 모두 확장하지 않고도 원래 배열의 합과 두 번 반복한 배열만으로 답을 구할 수 있어, k가 매우 큰 경우에도 효율적으로 동작합니다.