<分区>
我有一个包含偶数个元素的数组,我必须选择 n/2(n=数组大小),配对并计算它们的 GCD,使得它们的 GCD 之和为最大值,一旦我们使用数组中的这些元素,我们不能再使用它们。
示例 1: `
Input : 8 24 12 16
Output : 20
解释:我们选择两对 (8,16) 和 (12,24),因为它们的 GCD 之和最大。 如果我们选择其他一些对,比如 (8,12) 和 (24,16),它们的 GCD 之和将为 4+4 =8。
示例 2:
Input : 12 10 36 25 36 16
Output: 45
解释:我们选择以下 3 对:(36,36)、(10,25) 和 (12,16),因为它们的 GCD 之和为 36+5+4 = 45。
我们的方法:
for i in range(0,n):
max = 0;
for j in range(i+1,n):
temp = gcd(a[i], a[j]) // standard func to find GCD
if(max<temp):
store i and j
store max gcd every time and finally make a[i] and a[j] =0 to mark the visited elements
已编辑 约束:最大元素数 = 20,a[i]< 10^9.
您能否建议一种算法来以最少的时间复杂度最佳地满足上述测试用例? 因为我的方法在多个测试用例上都失败了。