Hàm xoay (Rotate Function) trong C++

Mô tả bài toán

Cho mảng A độ dài n. Xoay phải k vị trí thành Bk. Định nghĩa F(k) = Σ i * Bk[i]. Tìm max F(k) với k = 0..n-1.

Ví dụ: A=[4,3,2,6] → F(0)=25, F(1)=16, F(2)=23, F(3)=26 → max = 26.

Giải thuật Công thức truy hồi O(n)

Mối liên hệ: F(k) = F(k-1) + sum(A) - n * A[n-k].

1. Tính F(0) và sum = Σ A[i].
2. Duyệt k = 1..n-1: F(k) = F(k-1) + sum - n * A[n-k].
3. Theo dõi max.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int n = A.size();
        if (n == 0) return 0;
        ll sum = 0, f0 = 0;
        for (int i = 0; i < n; i++) {
            sum += A[i];
            f0 += 1LL * i * A[i];
        }
        ll ans = f0, cur = f0;
        for (int k = 1; k < n; k++) {
            cur += sum - 1LL * n * A[n - k];
            ans = max(ans, cur);
        }
        return ans;
    }
};

int main() {
    vector<int> v = {4,3,2,6};
    Solution ob;
    cout << ob.maxRotateFunction(v); // 26
    return 0;
}

Độ phức tạp

• Thời gian: O(n).
• Không gian: O(1).