정수 배열이 주어졌을 때, 먼저 배열의 접두사(첫 번째 요소)를 가져와 -1을 곱한 뒤, 배열의 누적 합(prefix sum)을 계산하고, 마지막으로 생성된 접두사 배열에서 최대 합을 구하는 것이 이 문제의 목표입니다.
접두사 배열의 생성 방식
prefixArray[0] = 배열의 첫 번째 요소
prefixArray[1] = prefixArray[0] + arr[1]
prefixArray[2] = prefixArray[1] + arr[2]
prefixArray[3] = prefixArray[2] + arr[3] … 등의 방식으로 생성됩니다.
입출력 예시
입력 − int arr[] = {2, 4, 1, 5, 2}
출력 − 접두사 배열: -2 2 3 8 10 / 배열의 접두사에 -1을 곱해 얻을 수 있는 최대 합: 21
설명 − 정수 배열이 주어집니다. 먼저 배열의 접두사인 2를 가져와 -1을 곱하면 새 배열은 {-2, 4, 1, 5, 2}가 됩니다. 이 배열로 접두사 배열 {-2, 2, 3, 8, 10}을 만든 뒤, 마지막 단계에서 합을 최대화하면 -2+2+3+8+10 = 21이 되어 최종 출력값은 21입니다.
입력 − int arr[] = {-1, 4, 2, 1, -9, 6}
출력 − 접두사 배열: 1 5 7 8 -1 5 / 배열의 접두사에 -1을 곱해 얻을 수 있는 최대 합: 19
설명 − 정수 배열이 주어집니다. 먼저 배열의 접두사인 -1을 가져와 -1을 곱하면 새 배열은 {1, 4, 2, 1, -9, 6}이 됩니다. 이 배열로 접두사 배열 {1, 5, 7, 8, -1, 5}을 만든 뒤, 마지막 단계에서 합을 최대화하면 1+5+8+5 = 19가 되어 최종 출력값은 19입니다.
아래 프로그램에 사용된 접근 방식
정수 배열과 임시 변수 x(-1)를 선언한 뒤, arr[0] = arr[0] * x로 설정합니다.
배열의 크기를 계산하고 접두사 배열 prefix_arry[size]를 선언합니다. create_prefix_arr(arr, size, prefix_array) 함수를 호출해 주어진 배열로부터 접두사 배열을 생성한 후 출력합니다.
최대 합을 저장할 maximize_sum(prefix_array, size) 함수를 호출합니다.
void create_prefix_arr(int arr[], int size, int prefix_array[]) 함수 내부
prefix_array[0]을 arr[0]으로 설정합니다.
i가 0부터 배열 크기까지 FOR 반복문을 실행하며, 반복 안에서 prefix_array[i] = prefix_array[i-1] + arr[i]로 설정합니다.
int maximize_sum(int prefix_array[], int size) 함수 내부
임시 변수 temp를 선언하고 -1로 초기화합니다.
i가 0부터 배열 크기까지 FOR 반복문을 실행하며, 반복 안에서 temp = max(temp, prefix_array[i])로 갱신합니다.
arr[temp + 1] 크기의 배열을 선언하고 모든 요소를 0으로 초기화합니다.
i가 0부터 배열 크기까지 FOR 반복문을 실행하며, 반복 안에서 arr[prefix_array[i]]++로 각 값의 빈도를 계수합니다.
임시 변수 max_sum을 0으로 선언하고, 변수 i를 temp 값으로 설정합니다.
i > 0인 동안 WHILE 반복문을 실행합니다. arr[i] > 0이면 max_sum에 i를 더하고 arr[i-1]과 arr[i]를 각각 1씩 감소시키고, 그렇지 않으면 i를 1 감소시킵니다.
max_sum을 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
#define Max_size 5
//접두사 배열 생성
void create_prefix_arr(int arr[], int size, int prefix_array[]) {
prefix_array[0] = arr[0];
for(int i=0; i<size; i++) {
prefix_array[i] = prefix_array[i-1] + arr[i];
}
}
//접두사 배열의 최대 합 찾기
int maximize_sum(int prefix_array[], int size) {
int temp = -1;
for(int i = 0; i < size; i++) {
temp = max(temp, prefix_array[i]);
}
int arr[temp + 1];
memset(arr, 0, sizeof(arr));
for(int i = 0; i < size; i++) {
arr[prefix_array[i]]++;
}
int max_sum = 0;
int i = temp;
while(i>0) {
if(arr[i] > 0) {
max_sum = max_sum + i;
arr[i-1]--;
arr[i]--;
} else {
i--;
}
}
return max_sum;
}
int main() {
int arr[] = {2, 4, 1, 5, 2};
int x = -1;
arr[0] = arr[0] * x;
int size = sizeof(arr) / sizeof(arr[0]);
int prefix_array[size];
//접두사 배열을 생성하는 함수 호출
create_prefix_arr(arr, size, prefix_array);
//접두사 배열 출력
cout<<"Prefix array is: ";
for(int i = 0; i < size; i++) {
cout << prefix_array[i] << " ";
}
//접두사 배열의 최대 합 출력
cout<<"\nMaximize the sum of array by multiplying prefix of array with -1 are:" <<maximize_sum(prefix_array, size);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Prefix array is: -2 2 3 8 10 Maximize the sum of array by multiplying prefix of array with -1 are: 21