arrays - 将一个数组分成两部分，使每个部分的元素乘积之和最大化

Question

我想将一个数组分成两部分。如果每个部分元素的乘积等于p1，p2。我们的目标是使 p1+p2 最大化。你能在多项式复杂性中找到它吗？谢谢

Answer 1

由于没有负面元素，只需执行以下操作：

foreach element in array
    if element < 1
         add to list1
    else
         add to list2

最大化产品的总和并在线性时间内运行。然后：

product1 = 1
foreach element in list1
    product1 = product1 * element

等等。请注意，这将导致空集的乘积为 1 - 这是正确的。