C++에서 i < j < k < l 조건으로 arr[j] - arr[i] + arr[l]

문제 개요

정수 배열이 주어졌을 때, 인덱스가 i < j < k < l 조건을 만족하도록 하면서 다음 표현식의 값을 최대화하는 것이 목표입니다.

arr[j] - arr[i] + arr[l] - arr[k]

가장 직관적인 해결 방법은 배열의 모든 요소를 순회하며 가능한 인덱스 조합마다 표현식 값을 계산하는 것입니다. 계산한 값이 지금까지 찾은 최댓값보다 크면 저장해 두고, 탐색이 끝나면 그 값을 반환합니다.

예제 1

arr[] = { 1, 2, 3, 4 }

출력:

위 표현식의 최댓값 : 2

설명: i < j < k < l 조건에서 i = 0, j = 1, k = 2, l = 3을 선택하면,

arr[j] - arr[i] + arr[l] - arr[k] = 2 - 1 + 4 - 3 = 1 + 1 = 2

예제 2

arr[] = { 5, 5, 5, 5, 5 }

출력:

위 표현식의 최댓값 : 0

설명: 모든 요소의 값이 같으므로 i, j, k, l을 어떻게 선택하더라도,

arr[j] - arr[i] + arr[l] - arr[k] = 5 - 5 + 5 - 5 = 0

풀이 접근 방법

정수 배열 a[]에 숫자들을 저장합니다.
maximizeSum(int arr[], int n) 함수는 배열과 그 길이 n을 입력받아, i < j < k < l 조건을 만족하는 arr[j] - arr[i] + arr[l] - arr[k]의 최댓값을 반환합니다.
변수 sum은 arr[j] - arr[i]와 arr[l] - arr[k]의 합을 임시로 저장하는 데 사용됩니다.
최댓값을 저장할 변수 maxx를 arr[0]으로 초기화합니다.
네 개의 중첩 반복문을 사용해 i = 0, j = 1, k = 2, l = 3부터 시작하여 i < n-3, j < n-2, k < n-1, l < n 범위까지 배열을 탐색합니다.
각 인덱스 조합(i, j, k, l)에 대해 arr[j] - arr[i] + arr[l] - arr[k]를 계산하여 sum에 저장합니다.
현재 sum이 maxx보다 크거나 같으면 maxx를 갱신합니다.
모든 탐색이 끝나면 maxx를 결과로 반환합니다.

이 방법은 네 개의 인덱스를 모두 확인하는 브루트 포스(완전 탐색) 방식으로, 시간 복잡도는 O(n⁴)입니다. 배열의 크기가 작을 때는 충분히 실용적이지만, 큰 입력에서는 사전 계산을 활용한 O(n) 최적화 기법을 고려할 수 있습니다.

C++ 구현 예제

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

// 선택된 수들의 합을 최대화하는 함수
int maximizeSum(int arr[], int n) {
    int sum = 0;
    int maxx = arr[0];
    for(int i = 0; i < n-3; i++)
        for(int j = i+1; j < n-2; j++)
            for(int k = j+1; k < n-1; k++)
                for(int l = k+1; l < n; l++) {
                    sum = arr[j] - arr[i] + arr[l] - arr[k];
                    if(sum >= maxx)
                        maxx = sum;
                }
    return maxx;
}

int main(){
    int a[] = {5, 3, 9, 2, 20};
    int n = sizeof(a) / sizeof(a[0]);
    cout << "최대화된 값 : " << maximizeSum(a, n);
    return 0;
}

실행 결과

최대화된 값 : 24