Cho mảng n phần tử, phép toán: chọn hai phần tử, thay phần tử lớn hơn bằng hiệu tuyệt đối. Lặp cho đến khi tất cả bằng nhau. Tìm tổng tối đa. Ví dụ [9,12,3,6] → 12 (tất cả thành 3).
Phép toán tương đương với tìm GCD của mảng. Giá trị cuối cùng là GCD, tổng = GCD * n.
Ví dụ
#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); }
Kết quả
The maximum sum is: 12