C++에서 허용되는 주어진 배열의 회전만 사용하여 Sum( i*arr[i])의 최대값 찾기

이 문제에서는 n개의 요소로 구성된 배열 arr[]이 제공됩니다. 주어진 배열에서만 회전이 허용되는 Sum( i*arr[i])의 최대값을 찾아야 합니다. (i*arr[i])의 최대 합을 찾기 위해 원하는 만큼 회전을 수행할 수 있습니다.

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

입력

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

출력

43

설명

최대값을 얻기 위해 배열을 한 번 회전합니다. 회전 후 배열은 {2, 4, 1, 3, 7}

합계 =0*2 + 1*4 + 2*1 + 3*3 + 4*7 =0 + 4 + 2 + 9 + 28 =43

솔루션 접근 방식

문제에 대한 간단한 해결책은 배열을 n번 회전하는 것입니다. 각 회전 후에 sum(i*arr[i])을 찾고 모든 값의 최대값을 반환합니다. 이것은 훌륭하지만 시간 복잡도는 O(n2)입니다. 문제에 대한 보다 효율적인 솔루션은 공식을 사용하여 회전 없이 sum(i*arr[i]) 값을 찾는 것입니다.

공식을 수학적으로 유도해 보겠습니다.

Let the sum after k rotation is equal to sum(k).
sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => eq 1

이제 합계가 되는 값을 회전합니다.

sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => eq 2 Subtracting eq2 - eq 1
sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1]
sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]

마찬가지로 sum(2) - sum(1),

sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]

방정식 일반화,

sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]

이것을 사용하여 sum(0)을 사용하여 sum(k)의 값을 찾을 수 있습니다.

이제 솔루션에서 배열의 모든 값의 합을 찾은 다음 sum(0)의 값을 찾습니다. 루프를 사용하여 1에서 n까지 sum(k)의 모든 값을 찾습니다. 그리고 최대값을 반환합니다.

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

예

#include <iostream>
using namespace std;
int findMaxSumRotation(int arr[], int n){
   int arrSum = 0;
   int currSum = 0;
   for (int i=0; i<n; i++){
      arrSum = arrSum + arr[i];
      currSum = currSum+(i*arr[i]);
   }
   int maxSum = currSum;
   for (int j=1; j<n; j++){
      currSum = currSum + arrSum-n*arr[n-j];
      if (currSum > maxSum)
         maxSum = currSum;
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 1, 3, 7, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum value of sum(i*arr[i]) using rotations is "<<findMaxSumRotation(arr, n);
   return 0;
}

출력

The maximum value of sum(i*arr[i]) using rotations is 43