-
简单的解决方案是对每个元素进行配对，然后找到最大LCM，但其时间复杂性为O(n^2(
有其他解决方案可以降低的时间复杂度吗
示例
阵列=12，9，1，8
LCM(12,9(=36
LCM(12,1(=12
LCM(12,8(=24
LCM(9，1(=9
LCM(9，8(=72
LCM(1.8(=8
所以，最大值是72。
#include<iostream>
#include<limits.h>
using namespace std;
void lcm(int a[],int n)
{
int i,j,k,l,s,lc=INT_MIN;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
s=a[i]<a[j]?a[i]:a[j];
l=a[i]>a[j]?a[i]:a[j];
for(k=0;k<s;k++)
{
if(l*(k+1)%s==0&&lc<l*(k+1))
{
lc=l*(k+1);
break;
}
}
}
}
cout<<"max lcm possible for a pair is= "<<lc;
}
int main()
{
int a[20],n,i;
cout<<"enter n= ";
cin>>n;
cout<<"enter an array= ";
for(i=0;i<n;i++)
{
cin>>a[i];
}
lcm(a,n);
}
**该代码是用c++编写的，不建议进行优化**