정수 요소로 이루어진 임의의 크기를 가진 배열이 주어졌을 때, 지정된 범위 내에서 배열의 어느 인덱스에서든 시작할 수 있는 부분 배열(subarray)을 만들어 얻을 수 있는 최대 합을 구하는 것이 이 글의 목표입니다. 이 문제는 세그먼트 트리(Segment Tree)를 활용하면 효율적으로 해결할 수 있으며, 여러 번의 범위 질의가 필요한 상황에서 특히 유용합니다.
입출력 예시
입력 − int arr[] = { 3, 2, -1, 6, 7, 2 }, first = 0, last = 5
출력 − 주어진 범위에서의 최대 부분 배열 합: 19
설명 − 양수와 음수가 모두 포함된 배열과 0부터 5까지, 즉 배열의 모든 인덱스를 포함하는 범위가 주어졌습니다. 이 경우 전체 배열의 합인 3 + 2 + (-1) + 6 + 7 + 2 = 19가 최대 부분 배열 합이 됩니다.
입력 − int arr[] = {-2, 1, 3, 4, 8, 9, 23}, first = 0, last = 3
출력 − 주어진 범위에서의 최대 부분 배열 합: 8
설명 − 이번에는 0부터 3까지의 인덱스만을 포함하는 범위가 주어졌습니다. 해당 범위 내에서 최대 합을 만드는 부분 배열은 1 + 3 + 4 = 8입니다.
프로그램에서 사용하는 접근 방식
max_val, max_temp, total, sub_sum을 멤버 변수로 갖는 트리 구조체를 생성하고, 기본 생성자에서 이 값들을 매우 작은 값(-MAX)으로 초기화합니다.
두 노드를 병합하는 set_nodes 메서드를 만듭니다. max_val은 max(left.max_val, left.total + right.max_val), max_temp는 max(right.max_temp, right.total + left.max_temp), total은 left.total + right.total, sub_sum은 max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val})로 설정한 뒤 노드를 반환합니다.
트리를 실제로 구축하는 build_tree 메서드를 생성합니다.
first == last라면 total, max_temp, max_val, sub_sum을 모두 arr[first]로 설정하고 반환합니다.
그렇지 않으면 build_tree(node, arr, first, temp, 2 * inx)와 build_tree(node, arr, temp + 1, last, 2 * inx + 1)를 재귀적으로 호출한 후, node[inx]를 set_nodes(node[2 * inx], node[2 * inx + 1])의 결과로 설정합니다.
create_tree 메서드를 만들어 temp를 (int)(ceil(log2(size)))로 설정한 뒤, 트리 노드 객체, 배열, 0, 배열 크기 - 1, 1을 인자로 전달하며 build_tree()를 호출합니다.
최대 부분 배열 합을 찾는 maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx) 메서드를 생성합니다.
temp > temp_4 또는 temp_2 < temp_3이라면 현재 구간이 질의 범위와 겹치지 않으므로 널(null) 노드를 반환합니다.
temp >= temp_3 && temp_2 <= temp_4라면 현재 구간이 질의 범위에 완전히 포함되므로 node[inx]를 그대로 반환합니다.
그 외의 경우에는 왼쪽 자식에 대해 maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx), 오른쪽 자식에 대해 maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1)를 호출합니다.
결과를 set_nodes(left, right)로 병합하여 반환합니다.
maximum_subarray(Tree* node, int first, int last, int size) 메서드를 생성합니다.
maximum_sub(node, 0, size - 1, first, last, 1)를 호출합니다.
temp.sub_sum을 반환합니다.
main() 함수에서는 다음 작업을 수행합니다.
양수와 음수 값을 포함하는 정수 배열을 선언하고 배열의 크기를 계산합니다.
첫 번째 인덱스부터 마지막 인덱스까지의 범위를 정의합니다.
maximum_subarray(node, first, last, size)를 호출하여 주어진 범위 내의 최대 부분 배열 합을 계산합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define MAX 0x3f3f
struct Tree{
int max_val;
int max_temp;
int total;
int sub_sum;
Tree(){
max_val = max_temp = sub_sum = -MAX;
total = -MAX;
}
};
Tree set_nodes(Tree left, Tree right){
Tree node;
node.max_val = max(left.max_val, left.total + right.max_val);
node.max_temp = max(right.max_temp, right.total + left.max_temp);
node.total = left.total + right.total;
node.sub_sum = max({left.sub_sum, right.sub_sum, left.max_temp + right.max_val});
return node;
}
void build_tree(Tree* node, int arr[], int first, int last, int inx){
if(first == last){
node[inx].total = arr[first];
node[inx].max_temp = arr[first];
node[inx].max_val = arr[first];
node[inx].sub_sum = arr[first];
return;
}
int temp = (first + last) / 2;
build_tree(node, arr, first, temp, 2 * inx);
build_tree(node, arr, temp + 1, last, 2 * inx + 1);
node[inx] = set_nodes(node[2 * inx], node[2 * inx + 1]);
}
Tree* create_tree(int arr[], int size){
int temp = (int)(ceil(log2(size)));
int n = 2 * (int)pow(2, temp) - 1;
Tree* node = new Tree[n];
build_tree(node, arr, 0, size - 1, 1);
return node;
}
Tree maximum_sub(Tree* node, int temp, int temp_2, int temp_3, int temp_4, int inx){
if(temp > temp_4 || temp_2 < temp_3){
Tree nullNode;
return nullNode;
}
if(temp >= temp_3 && temp_2 <= temp_4){
return node[inx];
}
int mid = (temp + temp_2) / 2;
Tree left = maximum_sub(node, temp, mid, temp_3, temp_4, 2 * inx);
Tree right = maximum_sub(node, mid + 1, temp_2, temp_3, temp_4, 2 * inx + 1);
Tree result = set_nodes(left, right);
return result;
}
int maximum_subarray(Tree* node, int first, int last, int size){
Tree temp = maximum_sub(node, 0, size - 1, first, last, 1);
return temp.sub_sum;
}
int main(){
int arr[] = { 3, 2, -1, 6, 7, 2 };
int size = sizeof(arr) / sizeof(arr[0]);
Tree* node = create_tree(arr, size);
int first = 0;
int last = 5;
int sub_sum = maximum_subarray(node, first, last, size);
cout<< "Maximum Subarray Sum in a given Range is: "<< sub_sum;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Maximum Subarray Sum in a given Range is: 19
시간 복잡도
이 접근 방식에서 세그먼트 트리를 구축하는 데는 O(N)의 시간이 소요되며, 이후 각 범위 질의는 O(log N) 만에 처리됩니다. 따라서 동일한 배열에 대해 여러 번 서로 다른 범위의 최대 부분 배열 합을 구해야 하는 경우, 매번 O(N²)의 완전 탐색을 수행하는 것보다 훨씬 효율적입니다.