ধরুন আমাদের একটি অ্যারে আছে। আমাদের সাবয়েরের সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করতে হবে, যার 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
