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,
R J schrieb: 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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe