C++로 배열 요소가 1~n 범위일 때 인접 요소 절대 차이 합의 최댓값 구하기

이 문제에서는 1부터 n 사이의 값을 가지는 n개의 정수로 이루어진 배열이 주어집니다. 우리가 해야 할 작업은 다음 식의 최댓값을 찾는 프로그램을 작성하는 것입니다.

|arr[0] – arr[1]| + |arr[1] – arr[2]| + … + |arr[n – 2] – arr[n – 1]|

문제 이해하기

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

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

출력 − 3

설명 −

최대 합은
|1-3| + |2-1| = 3

해결 접근 방식

이 문제를 해결하는 가장 단순한 방법은 배열의 모든 순열(permutation)을 생성하고, 각 순열에서 계산되는 값들 중 최댓값을 찾는 것입니다. 하지만 이 방법은 시간 복잡도가 매우 큽니다.

더 효율적인 방법은 n의 각 값에 대해 최댓값을 일반화한 뒤, 이를 바탕으로 일반 공식을 도출하는 것입니다.

n의 값에 따른 최대 합을 정리하면 다음과 같습니다.

n = 1일 때 최대 합 = 0
n = 2일 때 최대 합 = 1
n = 3일 때 최대 합 = 3
n = 4일 때 최대 합 = 7
n = 5일 때 최대 합 = 11
즉, 최댓값은 0, 1, 3, 7, 11… 의 패턴을 따릅니다.

이 패턴으로부터 도출할 수 있는 일반 공식은 다음과 같습니다.

((n * n / 2) - 1)

구현 예제

위 해결 방법의 동작을 보여주는 프로그램입니다.

#include <iostream>
using namespace std;
int maxAbsVal(int n) {
   if (n == 1)
      return 0;
   return ((n*n/2) - 1);
}
int main() {
   int n = 4;
   cout<<"The maximum sum of absolute difference is "<<maxAbsVal(n);
   return 0;
}

출력 결과

The maximum sum of absolute difference is 7

n = 4인 경우 공식에 대입하면 (4 × 4 / 2) - 1 = 7이 되어, 예상한 최댓값과 일치하는 것을 확인할 수 있습니다. 이처럼 일반 공식을 사용하면 순열을 일일이 생성하지 않고도 O(1)의 시간 복잡도로 답을 구할 수 있습니다.