arrays - 最大製品昇順サブシーケンス

Question

サイズ n の (負でない) 整数配列で、サイズ k の最大積の昇順サブシーケンスを見つける方法。良い解決策が見つかりませんでした。サブシーケンスは連続している必要はありません。例: サイズ 3 の 10,1,3,9,7,8,5 で 3,7,8。

Answer 1

以前に見た問題に還元してみてください。

1. サブシーケンスの最大長増加問題を解きます。
2. 最大合計増加サブシーケンス問題を解きます。
3. 積を合計に変換する方法を考えてみてください。(ヒント: 対数、なぜ?)
4. 最大積増加部分列問題を解きます。

Answer 2

Haskell ではこれを行うことができますが、n が大きい場合はあまり高速ではない可能性があります。

import Data.List (maximumBy, sort, subsequences)

maxSubProduct k = 
  maximumBy (\a b -> compare (foldr (*) 1 a) (foldr (*) 1 b)) 
  . filter (\x -> x == sort x) 
  . filter ((==k) . length) 
  . subsequences


OUTPUT:
*Main> maxSubProduct 3 [10,1,3,9,7,8,5]
[3,7,8]