在数字数组中找到具有特定倍数的最高产品

Question

任务是给定一个整数数组，找出数组中两个数字的最大乘积，即 3 的倍数。

</script>
arr = [-9, -11, 4, 6, 9, 7]; 
arr2 = [-11, 4, 6, 7]; 
arr3 = [11, 3, 5]

function findProduct(arr) {
  let maxProduct = 0;

  for(let i = 0; i < arr.length - 1; i++) {
    
    
    for(let j = i + 1; j < arr.length; j++) {
      let product = arr[i] * arr[j]

      if(product % 3 !== 0) continue;
      
      if(product > maxProduct) {
        maxProduct = product
      }
    }
  }

  return maxProduct
}

console.log(findProduct(arr))
console.log(findProduct(arr2))
console.log(findProduct(arr3))
</script>
´´´´

Answer 1

一个O(N)次，O(1)额外的space算法：

遍历数组，跟踪两个变量：max_multiple_of_three和min_multiple_of_three
遍历数组，跟踪两个变量：largest_number_in_array（不应与 max_multiple of three 具有相同的索引）和 smallest_number_in_array（不应具有相同的索引作为 min_multiple_of_three)
答案将是 max_multiple_of_three * largest_number_in_array 或 min_multiple_of_three * smallest_number_in_array

示例 1：

arr = [-9, -11, 4, 6, 9, 7]

max_multiple_of_three = 9
min_multiple_of_three = -9
largest_number_in_array = 7
smallest_number_in_array = -11

ans = max(-9*-11, 9*7) = 99

示例 2：

arr = [-11, 4, 6, 7]

max_multiple_of_three = 6
min_multiple_of_three = 6
largest_number_in_array = 7
smallest_number_in_array = -11

ans = max(6*-11, 6*7) = 42

在数字数组中找到具有特定倍数的最高产品

In an array of numbers find higest product with specific multiple

arrays

algorithm

sorting

integer

示例 1：

示例 2：