CODEWITHSUNDEEP
arraysalgorithminteger
scv
scv

Reputation: 520

Maximum product ascending sub sequence

How to find maximum product ascending sub sequence of size k in an (non negative) integer array of size n. I did not find any good solution. The sub sequence need not be contiguous. For ex: 3,7,8 in 10,1,3,9,7,8,5 for size 3.

Upvotes: 1

Views: 690

Answers (2)

Anil Vaitla
Anil Vaitla

Reputation: 2978

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.

Upvotes: 1

גלעד ברקן
גלעד ברקן

Reputation: 23955

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]

Upvotes: 1

Related Questions