최대값 |arr[0] – arr[1] - + |arr[1] – arr[2] - + … +|arr[n – 2] – arr[n – 1] - 요소가 1에서 1 사이일 때 C++의 n

이 문제에서는 [1,n] 범위의 n개의 정수 배열이 제공됩니다. 우리의 임무는 |arr[0] – arr[1] - + |arr[1] – arr[2] - + … +|arr[n – 2] – arr[ n – 1].

문제를 이해하기 위해 예를 들어 보겠습니다.

입력 - 배열={1, 2, 3}

출력 - 3

설명 -

max sum is
|1-3|+|2-1| = 3

이 문제를 해결하기 위해 간단한 접근 방식은 배열에서 모든 순열을 만드는 것입니다. 그리고 순열에서 모든 값의 최대값을 찾습니다. 보다 효과적인 방법은 n의 각 값에 대한 최대값을 모두 일반화한 다음 일반 공식을 만드는 것입니다.

그래서

Maximum sum for (n = 1) = 0
Maximum sum for (n = 2) = 1
Maximum sum for (n = 3) = 3
Maximum sum for (n = 4) = 7
Maximum sum for (n = 5) = 11
So, the maximum value is 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