หาค่า Max ของ Sum(i*arr[i]) ด้วยการหมุนอาร์เรย์ใน C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] ขนาด n ต้องการหา ค่าสูงสุดของ Sum(i × arr[i]) โดยอนุญาตให้ หมุนอาร์เรย์ (Rotate) ได้ไม่จำกัดจำนวนครั้ง

ตัวอย่าง

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

Output: 43

คำอธิบาย: หมุนอาร์เรย์ 1 ครั้ง → {2, 4, 1, 3, 7}
Sum = 0×2 + 1×4 + 2×1 + 3×3 + 4×7 = 0 + 4 + 2 + 9 + 28 = 43

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force (หมุน n ครั้ง, คำนวณทุกครั้ง)

Time: O(n²) - ช้า

วิธีที่ 2: สูตรทางคณิตศาสตร์ (O(n))

ให้ sum(k) เป็นผลรวมหลังหมุน k ครั้ง

การนำสูตร:

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]
               = (Sum of all elements) - n*arr[n-1]

โดยทั่วไป: sum(k) - sum(k-1) = arrSum - n * arr[n-k]

ดังนั้น สามารถคำนวณ sum(k) จาก sum(k-1) ได้ใน O(1)

อัลกอริทึม

1. คำนวณ arrSum = ผลรวมสมาชิกทั้งหมด
2. คำนวณ currSum = sum(0)
3. ตั้ง maxSum = currSum
4. ลูป j = 1 ถึง n-1:
   • currSum = currSum + arrSum - n * arr[n-j]
   • อัปเดต maxSum
5. คืนค่า maxSum

โค้ดตัวอย่าง C++

#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 << "The maximum value of sum(i*arr[i]) using rotations is " << findMaxSumRotation(arr, n);
    return 0;
}

ผลลัพธ์

The maximum value of sum(i*arr[i]) using rotations is 43