C++의 배열 arr[]에서 abs(i – j) * min(arr[i], arr[j])의 최대값 찾기

이 문제에서 N개의 정수 값을 요구하는 배열이 주어집니다. 우리의 작업은 arrayarr[]에서 abs(i – j) * min(arr[i], arr[j])의 최대값을 찾는 것입니다.

문제 설명 − 두 요소의 최소값의 최대 곱 값과 해당 인덱스 간의 절대 차이를 찾아야 합니다. 즉, 두 값 i와 j에 대해 abs(i - j) * min(arr[i] , arr[j])을 최대화해야 합니다.

입력

arr[] = {5, 7, 3, 6, 4}

출력

16

설명

The maximum value is 16, between index 0 and 4
=> abs(0 - 4)*min(arr[0], arr[4])
=> 4*min(5, 4) => 4*4 = 16

솔루션 접근 방식

문제에 대한 간단한 해결책은 중첩 루프를 사용하는 것입니다. 우리는 두 개의 루프를 취하고 i와 j의 각 쌍에 대한 값을 계산할 것입니다. 그런 다음 찾은 모든 값의 최대값을 반환합니다.

이 접근 방식은 좋지만 O(n ² 차수의 시간 복잡도가 있습니다. ).

문제에 대한 효과적인 솔루션은 배열의 끝에서 다른 시작부터 두 개의 반복기 값을 사용하는 것입니다. 반복자의 각 값에 대해 필요한 값을 찾아 비교하고 최대 inmaxVal 변수를 저장합니다. 두 반복자가 서로 교차하고 마지막에 maxVal을 반환할 때까지 이 작업을 수행합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include<iostream>
using namespace std;
int calcMaxProdValue(int arr[], int n) {
   int maxVal = -100;
   int currentVal;
   int start = 0, end = n-1;
   while (start < end) {
      if (arr[start] < arr[end]) {
         currentVal = arr[start]*(end-start);
         start++;
      }
      else {
         currentVal = arr[end]*(end-start);
         end--;
      }
      maxVal = max(maxVal, currentVal);
   }
   return maxVal;
}
int main(){
   int arr[] = {5, 7, 3, 6, 4};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is "<<calcMaxProdValue(arr,n);
   return 0;
}

출력

The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is 16