arrays - 1つの配列を2つの部分に分割し、各部分の要素の積の合計を最大化します

Question

1つの配列を2つの部分に分割したいと思います。各部分の要素の積が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 になることに注意してください。これは正しいことです。