최대값 |arr[i] – arr[j] - + |i – j| C++에서

이 문제에서는 n개의 정수 배열이 제공됩니다. 우리의 임무는 |arr[i]-arr[j]|의 최대값을 찾는 프로그램을 만드는 것입니다. + |i-j|.

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

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

출력 - 4

설명 -

|arr[0] - arr[1]|+|0-1| = |4-1| + |-1| = 3+1 = 4
|arr[0] - arr[2]|+|0-2| = |4-2| + |-2| = 2+2 = 4
|arr[1] - arr[2 ]|+|1-2| = |1-2| + |1-2| = 1+1 = 2

이 문제를 해결하기 위해 무차별 대입을 사용하는 간단한 접근 방식이 있습니다. 두 개의 루프를 사용하고 최대 차이를 찾는 접근 방식입니다.

그러나 효율적인 접근 방식은 절대 함수의 속성을 사용하는 것입니다.

방정식을 해독하고 해를 구합시다.

arr[i] - arr[j] + i - j = (arr[i] + i) - (arr[j] + j)
arr[i] - arr[j] - i + j = (arr[i] - i) - (arr[j] - j)
-arr[i] + arr[j] + i - j = -{(arr[i]-i) -(arr[j]-j)}
-arr[i] + arr[j] - i + j = -{(arr[i]+i) - (arr[j]+j)}

첫째와 넷째가 같고 둘째와 넷째가 같다. 이것을 사용하여 arr[i]+- i 값을 저장할 두 개의 배열을 만듭니다.

array1은 값 arr[i] + i

array2는 값을 저장합니다 arr[i] - i

따라서 다음과 같은 두 값의 최대값을 찾습니다.

최대((최대(배열1)-최소(배열1)), (최대(배열2)-최소(배열2)))

예시

우리 솔루션의 구현을 보여주는 프로그램

#include<iostream>
using namespace std;
int maxDiff(int arr[], int n) {
   int ans = 0;
   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
         ans = max(ans, abs(arr[i] - arr[j]) + abs(i - j));
   return ans;
}
int main() {
   int array[] = { 5, 7, 1, 2 };
   int n = sizeof(array) / sizeof(array[0]);
   cout<<"The maximum value of |arr[i] - arr[j]| + |i-j| is "<<maxDiff(array, n);
   return 0;
}

출력

The maximum value of |arr[i] - arr[j]| + |i-j| is 7