สมมติว่าเรามีอาร์เรย์ขององค์ประกอบ n ค้นหาผลรวมสูงสุดขององค์ประกอบทั้งหมดเพื่อให้องค์ประกอบทั้งหมดเหมือนกัน เฉพาะการดำเนินการที่อนุญาตเท่านั้นคือการเลือกสององค์ประกอบและแทนที่องค์ประกอบที่ใหญ่กว่าด้วยความแตกต่างที่แน่นอนของทั้งสอง สมมติว่าองค์ประกอบเป็นเหมือน [9, 12, 3, 6] จากนั้นผลลัพธ์จะเป็น 12 ดังนั้นในตอนแรกแทนที่ A[1] ด้วย A[1] – A[3] =12 – 6 =6 ดังนั้นตอนนี้องค์ประกอบคือ [9, 6, 3, 6] จากนั้นแทนที่ A[ 3] กับ A[3] – A[2] =6 – 3 =3 ดังนั้นองค์ประกอบคือ [9, 6, 3, 3] จากนั้นแทนที่ A[0] ด้วย A[0] – A[1] =9 – 6 =3 องค์ประกอบก็คือ [3, 6, 3, 3] และสุดท้ายแทนที่ A[1] ด้วย A[1] – A[3] =6 – 3 =3 ดังนั้นองค์ประกอบก็คือ [3, 3, 3, 3] ทั้งหมดจึงเหมือนกัน และผลรวมคือ 12
ถ้าเราวิเคราะห์การดำเนินการ มันจะเป็น A[i] =A[i] – A[j] โดยที่ A[i]> A[j] เราจะเอาตัวเลขสองตัว แล้วแทนที่ค่าที่มากกว่าด้วยผลต่างสัมบูรณ์ของพวกมัน จากนั้นทำซ้ำขั้นตอนเหล่านี้จนเหมือนเดิม
ตัวอย่าง
#include<iostream>
#include<algorithm>
using namespace std;
int findSameElement(int arr[], int n) {
int gcd_val = arr[0];
for (int i = 1; i < n; i++)
gcd_val = __gcd(arr[i], gcd_val);
return gcd_val;
}
int getMaxSum(int arr[], int n) {
int value = findSameElement(arr, n);
return (value * n);
}
int main() {
int arr[] = {3, 9, 6, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum sum is: " << getMaxSum(arr, n);
} ผลลัพธ์
The maximum sum is: 12
