Как найти максимальную восходящую подпоследовательность размера k в (не отрицательном) целочисленном массиве размера n. Я не нашел подходящего решения. Подпоследовательность не должна быть смежной. Например: 3,7,8 в 10,1,3,9,7,8,5 для размера 3.Максимальный восходящий поднабор продукта
Попробуйте уменьшить проблему, которую вы видели раньше.
Немного сложно понять, что происходит в вашем ответе, но +1 для хорошей идеи. 3. Подсказка часть 2 - 'log ab = log a + log b'. – Dukeling
В целом я думаю, что важно показать общую стратегию атаки, казалось бы, трудных проблем. Один из методов, который вы пытаетесь сделать, сводится к проблеме, которую вы видели раньше. Я думаю, что максимальная возрастающая подпоследовательность является проблемой канонического динамического программирования. Поэтому сначала вы должны знать, как это сделать (так как вам понадобится общая стратегия динамического программирования). Тогда вы можете сделать это сложнее, если решить проблему с максимальной суммой увеличения подпоследовательности. Затем, заметив # 3, вы поймете, что ваша проблема сводится к # 2. Также # 3 был трюк журнала, который вы упомянули –
В Haskell, вы могли бы сделать это, хотя это может быть не очень быстро при больших п:
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]
Это выглядит ш. Опишите, что вы уже пробовали. –
Его не hw. Я просто смотрел на некоторые вопросы интервью и наткнулся на это. – scv
Приносим извинения, но было бы неплохо увидеть, что вы пробовали, чтобы мы могли помочь вам найти решение из вашего текущего метода. –