C ++中带有难看数字的子数组的最大长度
问题陈述
给定一个由N个元素组成的数组arr[]（0≤arr[i]≤1000）。任务是找到仅包含丑陋数字的子数组的最大长度。
丑数是仅素数为2、3或5的数。
下面的示例是系列中的几个数字：1、2、3、4、5、6、8、9、10、12、15，…
示例
如果输入数组为{1、2、7、9、120、810、374}，则答案为3，如-
丑数sis{9，120，810}的可能的最长子数组
算法
取一个unordered_set，然后在集合中插入所有小于1000的丑陋数字
使用两个名为current_max和max_so_far的变量遍历数组。
检查集中是否存在每个元素
如果找到一个丑陋的数字，则增加current_max并将其与max_so_far进行比较
如果current_max>max_so_far，则max_so_far=current_max。
每次发现不难看的元素时，请重置current_max=0。
示例
#include <bits/stdc++.h>
using namespace std;
unsigned getUglyNumbers(int n) {
int ugly[n];
int i2 = 0, i3 = 0, i5 = 0;
int next_multiple_of_2 = 2;
int next_multiple_of_3 = 3;
int next_multiple_of_5 = 5;
int next_ugly_no = 1;
ugly[0] = 1;
for (int i = 1; i < n; i++) {
next_ugly_no = min(next_multiple_of_2, min(next_multiple_of_3, next_multiple_of_5));
ugly[i] = next_ugly_no;
if (next_ugly_no == next_multiple_of_2) {
i2 = i2 + 1;
next_multiple_of_2 = ugly[i2] * 2;
}
if (next_ugly_no == next_multiple_of_3) {
i3 = i3 + 1;
next_multiple_of_3 = ugly[i3] * 3;
}
if (next_ugly_no == next_multiple_of_5) {
i5 = i5 + 1;
next_multiple_of_5 = ugly[i5] * 5;
}
}
return next_ugly_no;
}
int maxUglySubarray(int arr[], int n) {
unordered_set<int> s;
int i = 1;
while (1) {
int next_ugly_number = getUglyNumbers(i);
if (next_ugly_number > 1000)
break;
s.insert(next_ugly_number);
i++;
}
int current_max = 0, max_so_far = 0;
for (int i = 0; i < n; i++) {
if (s.find(arr[i]) == s.end())
current_max = 0;
else {
current_max++;
max_so_far = max(current_max,
max_so_far);
}
}
return max_so_far;
}
int main() {
int arr[] = {1, 2, 7, 9, 120, 810, 374};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum sub-array size of consecutive ugly numbers = " << maxUglySubarray(arr, n) << endl;
return 0;
}输出结果
当您编译并执行上述程序时。它产生以下输出-
Maximum sub-array size of consecutive ugly numbers = 3