Trong bài toán này, chúng ta được đưa ra một mảng arr [] gồm n phần tử. Chúng ta cần Tìm giá trị lớn nhất của Sum (i * arr [i]) chỉ với phép quay trên một mảng đã cho. Để tìm tổng lớn nhất của (i * arr [i]), chúng ta có thể thực hiện bất kỳ số phép quay nào.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
arr[] = {4, 1, 3, 7, 2} Đầu ra
43
Giải thích
Chúng ta sẽ xoay mảng một lần để có giá trị lớn nhất, Sau khi xoay mảng sẽ là {2, 4, 1, 3, 7}
Tính tổng =0 * 2 + 1 * 4 + 2 * 1 + 3 * 3 + 4 * 7 =0 + 4 + 2 + 9 + 28 =43
Cách tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là xoay mảng n lần. Sau mỗi lần xử lý, chúng ta sẽ tìm tổng (i * arr [i]) và trả về giá trị lớn nhất của tất cả các giá trị. Điều này thật tuyệt nhưng độ phức tạp về thời gian là bậc O (n2). Một giải pháp hiệu quả hơn cho vấn đề là tìm giá trị của sum (i * arr [i]) mà không sử dụng công thức xoay vòng.
Hãy suy ra công thức về mặt toán học,
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
Bây giờ, chúng ta sẽ xoay vòng các giá trị mà sau đó tổng sẽ trở thành,
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]
Tương tự cho sum (2) - sum (1),
sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]
Tổng quát phương trình,
sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]
Sử dụng điều này, chúng ta có thể tìm giá trị của sum (k) bằng cách sử dụng sum (0),
Bây giờ, trong giải pháp, chúng ta sẽ tìm tổng của tất cả các giá trị của mảng, sau đó tìm giá trị của sum (0). Sử dụng một vòng lặp, chúng ta sẽ tìm thấy tất cả các giá trị của sum (k) từ 1 đến n. Và trả lại giá trị tối đa.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The maximum value of sum(i*arr[i]) using rotations is 43