最大乘積遞增子序列

如何在大小爲n的（非負）整數數組中尋找最大乘積大小爲k的乘積子序列。我沒有找到任何好的解決方案。子序列不必是連續的。例如：尺寸爲3的10,1,3,9,7,8,5中的3,7,8。最大乘積遞增子序列

來源

2013-04-11 scv

這看起來像漢王。請描述你已經嘗試了什麼。 – 2013-04-11 00:39:12

它不是一個hw。我只是在看一些面試問題，並遇到了這個問題。 – scv 2013-04-11 20:29:59

我很抱歉，看到您嘗試過的內容仍然很高興，以便我們可以幫助您引導您使用當前方法提供的解決方案。 – 2013-04-11 20:51:32

嘗試降低至之前看過的問題。

解決最大長度增加的子序列問題。
解決最大和增加子序列問題。
想想產品如何轉換爲總和。（提示：對數，爲什麼？）
解決最大產品遞增的子序列問題。

來源

2013-04-11 00:29:54

找出答案中的內容有點困難，但+1是一個好主意。 3.提示第2部分 - 「log ab = log a + log b」。 – Dukeling 2013-04-11 07:40:10

總的來說，我認爲它顯示出攻擊看似棘手問題的總體策略非常重要。一種嘗試的方法是減少你以前見過的問題。我認爲最大長度增加子序列是一個典型的動態規劃問題。所以首先你必須知道如何去做（因爲你需要一般的動態編程策略）。然後你可以通過解決最大總和增加的子序列問題來使其變得更復雜。然後，一旦你注意到＃3，你意識到你的問題只是減少到＃2。＃3是你提到的日誌技巧 – 2013-04-11 18:16:10

在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]

來源

2013-04-11 00:30:34

最大乘積遞增子序列

回答

相關問題