数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学最大公约数大于1的最长子数组
数组是由存储在连续内存位置的相似数据集组成的集合。通过为数据库的特定基值定义一个偏移值，可以更轻松地评估每个元素的特定位置。该特定索引的基值为零，偏移值是两个特定索引之差的值。子数组是特定数组的一部分，可以定义为一组变量，这些变量共同具有多个值的标签。最长子数组是指所有元素都大于 K 的数组。这里最大和子数组的和为：
小于给定数据集。
等于给定数据集。
小于给定数据集。
要找到最长子数组的长度，我们只需要找出特定子数组中 1 的总数。注意：计数应该大于零的计数。最大公约数 (GCD) 是一种数学现象，我们找到可以将每个输入整数除以零余数的最大的整数值。这里的条件是，“GCD 大于 1”。这意味着给定的输入之间至少存在一个公共除数。
Input (array) : arr[] = {4, 3, 2, 2}
Output (after the process with sub-array operation) : 2
If we consider the subarray as {2, 2}, then we will get 2 as GCD. Which is > 1, is of maximum length.
在今天的文章中，我们将学习如何使用 C++ 编码环境查找最大公约数大于 1 的最长子数组。
查找最大公约数大于 1 的最长子数组的算法
在这个特定算法中，我们可以找出包含大于 1 的最大公约数的子数组。
步骤 1 - 开始。
步骤 2 - 声明用于该过程的变量。
步骤 3 - 设置并将其初始化为零值。
步骤 4 - 创建一个函数来评估该子数组的最大长度。
步骤 5 - 包含一个向量作为参数。
步骤 6 - 创建一个变量来获取答案。
步骤 7 - 设置并将其初始化为零值。
步骤 8 - 存储最大公约数大于 1 的最长子数组的值。
步骤 9 - 迭代循环以查找每个子数组的最大公约数。
步骤 10 - 用子数组的长度值替换答案。
步骤 11 - 如果子数组的最大公约数大于 1，则保存答案。
步骤 12 - 返回答案。
步骤 13 - 否则，再次运行循环并迭代它。
步骤 14 - 过程完成后终止。
查找最大公约数大于 1 的最长子数组的语法
int n;
cin >> n;
const int MAX_NUM = 100 * 1000;
static int dp[MAX_NUM];
for(int i = 0; i < n; ++i){
int x;
cin >> x;
int cur = 1;
vector<int> d;
for(int i = 2; i * i <= x; ++i){
if(x % i == 0){
cur = max(cur, dp[i] + 1);
cur = max(cur, dp[x / i] + 1);
d.push_back(i);
d.push_back(x / i);
}
}
if(x > 1){
cur = max(cur, dp[x] + 1);
d.push_back(x);
}
for(int j : d){
dp[j] = cur;
}
}
cout << *max_element(dp, dp + MAX_NUM) << endl;
按照上述算法，我们在这里编写了可能的语法来查找最大公约数大于 1 的最长子数组。
方法：-
方法 1 - 使用朴素方法查找最大公约数大于 1 的最长子数组的 C++ 程序。
方法 2 - 查找数组的最大公约数是否大于 1 的 C++ 程序。
使用朴素方法查找最大公约数大于 1 的最长子数组的 C++ 程序
在这个 C++ 代码中，我们应用了朴素方法，通过生成给定数组的所有可能的子数组来查找存在最大公约数大于 1 的最长子数组。
示例 1
#include <bits/stdc++.h>
using namespace std;
void maxSubarrayLen(int arr[], int n) {
int maxLen = 0;
for (int i = 0; i < n; i++) {
int gcd = 0;
for (int j = i; j < n; j++) {
gcd = __gcd(gcd, arr[j]);
if (gcd > 1)
maxLen = max(maxLen, j - i + 1);
else
break;
}
}
cout << maxLen;
}
int main() {
int arr[] = { 410, 16, 7, 180, 222, 10, 33 };
int N = sizeof(arr) / sizeof(int);
maxSubarrayLen(arr, N);
return 0;
}
输出
3
查找数组的最大公约数是否大于 1 的 C++ 程序
在这个 C++ 代码中，我们尝试计算最大公约数，并且它能够检查它是否大于 1。
示例 2
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
if (a == 0)
return b;
return gcd(b%a, a);
}
void bestArray(int arr[], int n){
bool even[n] = {false};
int ans = 0;
for(int i = 0; i < n; i++){
ans = gcd(ans, arr[i]);
if(arr[i] % 2 == 0)
even[i] = true;
}
if(ans > 1)
cout << 0 << endl;
else {
ans = 0;
for(int i = 0; i < n-1; i++){
if(!even[i]){
even[i] = true;
even[i+1] = true;
if(arr[i+1]%2 != 0){
ans+=1;
}
else
ans+=2;
}
}
if(!even[n-1]){
ans+=2;
}
cout << ans << endl;
}
}
int main(){
int arr[] = {16, 10, 07, 81, 88, 32, 3, 42, 25};
int n = 9;
bestArray(arr, n);
int arr1[] = {16, 7};
n = 2;
bestArray(arr1, n);
int arr2[] = {10, 97, 2001};
n = 3;
bestArray(arr2, n);
}
输出
5 2 1
结论
通过本次讨论，我们可以了解如何找到最大公约数大于 1 的最长子数组。希望所写的算法和 C++ 代码能够清晰地让你了解这个过程在现实世界中的运作方式。
394 次浏览
