ฟังก์ชันหมุนใน C++

ให้อาร์เรย์ A ความยาว n กำหนด Bk = หมุน A ขวา k ตำแหน่ง ฟังก์ชันหมุน F(k) = Σ i * Bk[i] หา max F(k) สำหรับ k = 0..n-1

ตัวอย่าง: A=[4,3,2,6] → F(0)=25, F(1)=16, F(2)=23, F(3)=26 → คำตอบ 26

ขั้นตอนการแก้ปัญหา (Mathematical Optimization)

1. สังเกตว่า F(k) - F(k-1) = sum(A) - n * A[n-k]
2. คำนวณ F(0) โดยตรง แล้วใช้สูตรเวียนเกิดหา F(1)..F(n-1) ใน O(n)
3. รักษาค่าสูงสุด

โค้ดต้นฉบับใช้วิธี prefix/suffix sum ที่ซับซ้อนกว่า วิธีสูตรเวียนเกิดง่ายกว่า:

ตัวอย่างโค้ด C++ (ปรับปรุง)

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;

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

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

Input

[4,3,2,6]

Output

26