Giả sử chúng ta có một mảng gồm n phần tử. Tìm tổng lớn nhất có thể có của tất cả các phần tử sao cho tất cả các phần tử đều giống nhau. Chỉ hoạt động được phép là chọn bất kỳ hai phần tử nào và thay thế phần tử lớn hơn của chúng bằng hiệu số tuyệt đối của hai phần tử. Giả sử các phần tử như [9, 12, 3, 6]. Khi đó đầu ra sẽ là 12. Vì vậy, lúc đầu thay A [1] bằng A [1] - A [3] =12 - 6 =6. Vì vậy, bây giờ các phần tử là [9, 6, 3, 6], sau đó thay thế A [ 3] với A [3] - A [2] =6 - 3 =3. Vậy các phần tử là [9, 6, 3, 3]. Sau đó thay A [0] bằng A [0] - A [1] =9 - 6 =3. Vậy các phần tử là [3, 6, 3, 3]. Và cuối cùng thay A [1] bằng A [1] - A [3] =6 - 3 =3. Vậy các phần tử là [3, 3, 3, 3]. Vì vậy, tất cả đều giống nhau. Và tổng là 12
Nếu chúng ta phân tích phép toán, nó sẽ là A [i] =A [i] - A [j], trong đó A [i]> A [j]. Vì vậy, chúng tôi sẽ lấy hai số, sau đó thay thế giá trị lớn hơn bằng hiệu số tuyệt đối của chúng. Sau đó, lặp lại các bước này cho đến khi tất cả đều giống nhau.
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);
} Đầu ra
The maximum sum is: 12