ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ประกอบด้วย n องค์ประกอบ เราจำเป็นต้องค้นหาค่าสูงสุดของผลรวม ( i*arr[i]) โดยอนุญาตให้หมุนได้เฉพาะในอาร์เรย์ที่กำหนด สำหรับการหาผลรวมสูงสุดของ (i*arr[i]) เราสามารถทำการหมุนจำนวนเท่าใดก็ได้
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {4, 1, 3, 7, 2} ผลลัพธ์
43
คำอธิบาย
เราจะหมุนอาร์เรย์หนึ่งครั้งเพื่อให้ได้ค่าสูงสุด หลังจากอาร์เรย์การหมุนจะเป็น {2, 4, 1, 3, 7}
ผลรวม =0*2 + 1*4 + 2*1 + 3*3 + 4*7 =0 + 4 + 2 + 9 + 28 =43
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาง่ายๆ คือการหมุนอาร์เรย์ n ครั้ง หลังจากการหมุนแต่ละครั้ง เราจะหาผลรวม (i*arr[i]) และคืนค่าสูงสุดของค่าทั้งหมด ดีมาก แต่ความซับซ้อนของเวลาอยู่ในลำดับ O(n2) วิธีแก้ปัญหาที่มีประสิทธิภาพมากขึ้นคือการหาค่า sum(i*arr[i]) โดยไม่ต้องหมุนโดยใช้สูตร
มาหาสูตรทางคณิตศาสตร์กันเถอะ
Let the sum after k rotation is equal to sum(k). sum(0) = 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] => eq 1
ตอนนี้ เราจะหมุนเวียนค่าหลังจากที่ผลรวมจะกลายเป็น
sum(1) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] => eq 2 Subtracting eq2 - eq 1 sum(1) - sum(0) = 0*arr[n-1] + 1*arr[0] +...+ (n-1)*arr[n-2] - 0*arr[0] + 1*arr[1] +...+ (n-1)*arr[n-1] sum(1) - sum(0) = arr[0] + arr[1] + … arr[n-2 ] - (n - 1)*arr[n-1]
ในทำนองเดียวกันสำหรับ sum(2) - sum(1),
sum(2) - sum(1) = arr[0] + arr[1] + …. arr[n - 3] - (n - 1)*arr[n-2] + arr[n-1]
การสรุปสมการ
sum(k) - sum(k-1) = arr[0] + arr[1] + …. Arr[n - 1] - (n)*arr[n - k]
เมื่อใช้สิ่งนี้ เราสามารถหาค่าของ sum(k) โดยใช้ sum(0),
ในการแก้ปัญหา เราจะหาผลรวมของค่าทั้งหมดของอาร์เรย์ แล้วหาค่าของ sum(0) เมื่อใช้ลูป เราจะหาค่าทั้งหมดของ sum(k) ตั้งแต่ 1 ถึง n และคืนจำนวนสูงสุดให้
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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 = arrSum + arr[i];
currSum = 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
