Maximum Sum of i*arr[i] Among All Rotations ใน C++

ปัญหา

มีอาร์เรย์ arr หาค่าสูงสุดของ Σ(i × arr[i]) ในทุกการหมุน (rotation) ของอาร์เรย์

ตัวอย่าง

arr = {4, 8, 1, 5}
Rotations:
{4,8,1,5}: 0×4+1×8+2×1+3×5 = 25
{8,1,5,4}: 0×8+1×1+2×5+3×4 = 23
{1,5,4,8}: 0×1+1×5+2×4+3×8 = 37 ← Max
{5,4,8,1}: 0×5+1×4+2×8+3×1 = 23

วิธีง่าย (O(n²))

หมุนอาร์เรย์ n รอบ คำนวณผลรวมแต่ละรอบ หาค่าสูงสุด

วิธีมีประสิทธิภาพ (O(n))

ใช้สูตรความสัมพันธ์ระหว่างการหมุนติดกัน:

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

ตัวอย่างโค้ด C++ (ทั้งสองวิธี)

// วิธี O(n²)
int calculateMaxSum(int arr[], int n){
    int maxSum = 0, sum = 0;
    for (int i=0; i

ผลลัพธ์
The maximum sum of all the rotation of the array is 37