Tổng tối đa của i * arr [i] trong số tất cả các phép quay của một mảng nhất định trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr. Nhiệm vụ của chúng tôi là tạo một chương trình sẽ tìm tổng lớn nhất của i * arr [i] trong số tất cả các phép quay của mảng đã cho trong C ++.

Mô tả chương trình - Ở đây, chúng ta sẽ tìm tổng lớn nhất của tổng của tất cả các phần tử của mảng nhân với chỉ số {i * arr [i]} của chúng trong phép quay vòng.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng arr ={4, 8, 1, 5}

Đầu ra - 37

Giải thích -

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.

Một giải pháp đơn giản cho vấn đề này là tính tổng của tất cả các phần tử nhân với chỉ số của mỗi vòng quay. Và sau đó tìm tổng số tối đa của tất cả các phép quay. Đối với điều này, chúng tôi sẽ xoay mảng n lần và tính tổng cho mỗi biến và lưu trữ tổng của một biến maxSum nếu tổng của xoay hiện tại lớn hơn lần cuối cùng.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp này,

#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;
}

Đầu ra

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

Một giải pháp hiệu quả là sử dụng phép tính tổng của vòng quay tiếp theo bằng cách sử dụng vòng quay trước đó. Chúng tôi sẽ sử dụng công thức,

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

Sử dụng công thức này, chúng ta sẽ tìm thấy nextSum và ở cuối phần nội dung vòng lặp, chúng ta sẽ kiểm tra xem nextSum có lớn hơn maxSum hay không, nếu có thì maxSum =nextSum.

Ví dụ

Chương trình minh họa hoạt động của giải pháp này,

#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;
}

Đầu ra

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