Tìm giá trị lớn nhất của Tổng(i*arr[i]) chỉ cho phép xoay mảng trong C++

Mô tả vấn đề

Cho mảng arr[] n phần tử. Tìm giá trị lớn nhất của Sum(i * arr[i]) chỉ được phép thực hiện phép xoay vòng (rotation) mảng bất kỳ số lần.

Ví dụ minh họa

Đầu vào:

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

Đầu ra:

43

Giải thích:

Xoay mảng 1 lần: {2, 4, 1, 3, 7}

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

Phương pháp giải quyết

Cách đơn giản (O(n²)): Xoay mảng n lần, mỗi lần tính tổng.

Cách tối ưu (O(n)) - Công thức toán học:

Gọi sum(k) là tổng sau k lần xoay.

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

sum(1) - sum(0) = arr[0] + arr[1] + ... + arr[n-2] - (n-1)*arr[n-1]
Tổng quát: sum(k) - sum(k-1) = sum_array - n * arr[n-k]

=> sum(k) = sum(k-1) + sum_array - n * arr[n-k]

Tính sum(0) và sum_array một lần, sau đó lặp k từ 1 đến n-1 để tìm max.

Chương trình minh họa

#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 += arr[i];
        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 << "Giá trị lớn nhất của sum(i*arr[i]) bằng xoay là " << findMaxSumRotation(arr, n);
    return 0;
}

Kết quả đầu ra

Giá trị lớn nhất của sum(i*arr[i]) bằng xoay là 43