arrays - 最大乘积升序子序列

Question

如何在大小为 n 的（非负）整数数组中找到大小为 k 的最大乘积升序子序列。我没有找到任何好的解决方案。子序列不必是连续的。例如：10、1、3、9、7、8、5 中的 3、7、8 尺寸为 3。

Answer 1

Try reducing to a problem you've seen before.

1. Solve the max length increasing subsequence problem.
2. Solve max sum increasing subsequence problem.
3. Think about how a product can be converted to a sum. (hint: logarithm, why?)
4. Solve max product increasing subsequence problem.

Answer 2

In Haskell, you could do this, although it may not be very fast for large 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]