LCM的最大长度子数组等于C ++中的乘积
假设我们有一个数组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
-
如何加快以下问题陈述的执行速度？我有一个正确的解决方案，通过每一个测试的小输入。但是，它超过了较大输入的时间限制。我当前的实现是数组大小的二次型。 你的答案应该是基于1的，这意味着数组的第一个位置是1而不是0。 实施
-
本文向大家介绍查找三个小于或等于N的整数，以使它们的LCM最大-C ++，包括了查找三个小于或等于N的整数，以使它们的LCM最大-C ++的使用技巧和注意事项，需要的朋友参考一下 在本教程中，我们将编写一个基于LCM概念的程序。如标题所示，我们必须找到三个小于或等于LCM最大的给定数字的数字。 让我们来看一个例子。 在深入探讨问题之前，让我们看看什么是LCM并为其编写程序。 LCM是数字的最小公倍
-
给定一个只有和的数组，求取和数目相等的最大子数组的长度。例如，给定一个数组 编写递归函数。这个函数接受3个输入：一个数组-A，它的第一个元素的索引-start，最后一个元素的索引-end，并返回largestsubarray的大小。如果没有找到数量相等的子数组，则函数应返回0。 如何修复此代码？请帮忙。谢了。
-
我们将如何测试数组中每个子数组的长度等于子数组元素之和的P倍的所有子数组组合。 一个简短的示例：编辑： 期望的结果： 长度=2，P*元素之和=1。子序列是 编辑约束： 这些问题属于什么样的问题集（例如：NP-hard？）？语言：C#
-
考虑一个由 N 个整数组成的数组。找到最长的连续子数组，使其元素的平均值大于（或等于）给定数字 k。 显而易见的答案具有O（n^2）复杂度。我们能做得更好吗？
-
本文向大家介绍C ++中回文排列的最大偶数长度子字符串，包括了C ++中回文排列的最大偶数长度子字符串的使用技巧和注意事项，需要的朋友参考一下 问题陈述 给定一个字符串，任务是找到可以排列成回文式的子字符串的最大长度。 示例 如果输入字符串=“ 5432112356”，则答案为6，因为最大回文子字符串为“ 321123”，其长度为6 算法 如果子字符串的长度为奇数，则无法在最终解决方案中考虑它。