C++에서 주어진 배열의 모든 회전 중 i * arr[i]의 최대 합

이 문제에서는 배열 arr가 제공됩니다. 우리의 임무는 C++에서 주어진 배열의 모든 회전 중에서 i*arr[i]의 최대 합을 찾는 프로그램을 만드는 것입니다.

프로그램 설명 − 여기에서 회전에서 배열의 모든 요소의 합에 인덱스 {i * arr[i]}를 곱한 최대 합을 찾습니다.

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

입력 - 배열 arr ={4, 8, 1, 5}

출력 − 37

설명 -

All rotations with the sum of i*arr[i] :
{4, 8, 1, 5} = 4*0 + 8*1 + 1*2 + 5*3 = 25
{8, 1, 5, 4} = 8*0 + 1*1 + 5*2 + 4*3 = 23
{1, 5, 4, 8} = 1*0 + 5*1 + 4*2 + 8*3 = 37
{5, 4, 8, 1} = 5*0 + 4*1 + 8*2 + 1*3 = 23
The max sum of i*arr[i] is for third rotation.

이 문제에 대한 간단한 해결책은 모든 요소의 합에 각 회전의 인덱스를 곱한 값을 계산하는 것입니다. 그런 다음 모든 회전 합계의 최대값을 찾습니다. 이를 위해 배열을 n번 회전하고 각각에 대한 합계를 계산하고 현재 회전의 합계가 마지막 회전보다 큰 경우 maxSum 변수의 합계를 저장합니다.

예시

이 솔루션의 구현을 보여주는 프로그램,

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a>b)
      return a;
return b;
}
int calculateMaxSum(int arr[], int n){
   int maxSum = 0, sum = 0;
   for (int i=0; i<n; i++){
      sum = 0;
      for (int j=0; j<n; j++){
         int index = (i+j)%n;
         sum += j*arr[index];
      }
      maxSum = findMax(maxSum, sum);
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 8, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum sum of all the rotation of the array is "<<calculateMaxSum(arr, n);
   return 0;
}

출력

The maximum sum of all the rotation of the array is 37

효율적인 솔루션은 이전 회전을 사용하여 다음 회전의 합을 계산하는 것입니다. 우리는 공식을 사용할 것입니다,

nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1]*(n-1)

이 공식을 사용하여 nextSum을 찾고 루프 본문의 끝에서 nextSum이 maxSum보다 큰지 확인하고, 그렇다면 maxSum =nextSum입니다.

예시

이 솔루션의 작동을 설명하는 프로그램,

#include<iostream>
using namespace std;
int findMax(int a, int b){
   if(a > b)
      return a;
   return b;
}
int calculateMaxSum(int arr[], int n){
   int arraySum = 0, currentSum = 0, nextSum ;
   for (int i=0; i<n; i++){
      arraySum += arr[i];
      currentSum += i*arr[i];
   }
   int maxSum = currentSum;
   for (int i=1; i<n; i++){
      nextSum = currentSum - (arraySum - arr[i-1]) + arr[i-1] * (n1);
      currentSum = nextSum;
      maxSum = findMax(maxSum, nextSum);
   }
   return maxSum;
}
int main(){
   int arr[] = {4, 8, 1, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout<<"The maximum sum of all the rotation of the array is "<<calculateMaxSum(arr, n);
   return 0;
}

출력

The maximum sum of all the rotation of the array is 37