สมมติว่าเรามีอาร์เรย์ A เราต้องหาความยาวสูงสุดของอาร์เรย์ย่อย ซึ่ง LCM จะเหมือนกับผลคูณขององค์ประกอบของอาร์เรย์ย่อยนั้น หากไม่พบอาร์เรย์ย่อยนั้น ให้คืนค่า -1 สมมติว่าอาร์เรย์คือ {6, 10, 21} จากนั้นความยาวคือ 2 เนื่องจากอาร์เรย์ย่อย {10, 21} อยู่ที่นั่น ซึ่ง LCM คือ 210 และผลิตภัณฑ์คือ 210 ด้วย
แนวทางตรงไปตรงมา เราต้องตรวจสอบทุกอาร์เรย์ย่อยที่เป็นไปได้ที่มีความยาวมากกว่าหรือเท่ากับ 2 หากอาร์เรย์ย่อยเป็นไปตามเงื่อนไข ให้อัปเดตคำตอบเป็นค่าสูงสุดของคำตอบและความยาวของอาร์เรย์ย่อย
ตัวอย่าง
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
int maxLengthLCMSubarray(int arr[], int n) {
int len = -1;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
long long lcm = 1LL * arr[i];
long long product = 1LL * arr[i];
for (int k = i + 1; k <= j; k++) {
lcm = (((arr[k] * lcm)) / (gcd(arr[k], lcm)));
product = product * arr[k];
}
if (lcm == product) {
len = max(len, j - i + 1);
}
}
}
return len;
}
int main() {
int arr[] = {8, 2, 6, 10, 13, 21, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum Length: " << maxLengthLCMSubarray(arr, n);
} ผลลัพธ์
Maximum Length: 3
