सी ++ में उत्पाद के बराबर एलसीएम के साथ अधिकतम लंबाई उपसरणी

मान लीजिए कि हमारे पास एक सरणी A है। हमें उप-सरणी की अधिकतम लंबाई ज्ञात करनी है, जिसका LCM उस उप-सरणी के तत्वों के गुणनफल के समान है। यदि उस प्रकार का उप-सरणी नहीं मिलता है, तो -1 लौटाएं। मान लीजिए सरणी {6, 10, 21} है, तो लंबाई 2 है, क्योंकि उप-सरणी {10, 21} है, जिसका एलसीएम 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