資料結構
網路
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 次瀏覽
廣告