数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究用 C++ 找出 LCM 等于子数组中乘积最长的子数组
假设我们有一个数组 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
更新时间：21-10-2019
271 次浏览
广告