หาผลรวมอาร์เรย์สูงสุดหลังทำให้ทุกองค์ประกอบเท่ากันด้วยการลบซ้ำใน C++

สมมติว่ามีอาร์เรย์ 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