[Haskell-cafe] Re: Help with Bird problem 4.5.6: sequence of successive maxima

[Benedikt Huber]

R J schrieb:
> This Bird problem vexes me, in the first instance because it doesn't 
> seem to specify a unique solution:
> 
> Given a list xs = [x_1, x_2, . . . , x_n], the sequence of successive 
> maxima "ssm xs" is the
> longest subsequence [x_j1, x_j2, x_j3..x_jk] such that j_1 = 1 and j_m < 
> j_n => x_jm < x_jn.
> For example, xs = [3, 1, 3, 4, 9, 2, 10, 7] => ssm xs = [3, 4, 9, 10].  
> Define "ssm" in terms of "foldl".
Hi,
this problem is a variant of

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

discussed about a year ago:

http://www.mail-archive.com/haskell-cafe@haskell.org/msg39784.html
http://www.mail-archive.com/haskell-cafe@haskell.org/msg39844.html

In the latter mail, Chris Kuklewicz presents an (efficient) 
implementation. To solve the problem you stated, simply reuse `lnds`:

 > -- ssm [3, 1, 3, 4, 9, 2, 9, 10, 7] = [3,4,9,10]
 > ssm (x:xs) = x : lnds (filter (> x) xs)

benedikt

> 
>  From this specification, I infer:
> 
> ssm []           = []
> ssm [1]          = [1]
> ssm [1, 2, 3]    = [1, 2, 3]
> ssm [1, 0, 3, 2] = [1, 3]
> 
> However, what is ssm [1,0,100,2,3,4,5]?  Is it [1, 100] or [1, 2, 3, 4, 
> 5]?  I think the latter, but am not certain.  Whichever it is, what's 
> the solution?
> 
> Thanks.
> 
> 
> ------------------------------------------------------------------------
> Windows Live™ Groups: Create an online spot for your favorite groups to 
> meet. Check it out. 
> <http://windowslive.com/online/groups?ocid=TXT_TAGLM_WL_groups_032009>
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe