Longest Increasing Sub Seq

Find the longest consecutive sub-sequence of increasing numbers.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40:

(*
http://www.4clojure.com/problem/53

Given a vector of integers, find the longest consecutive sub-sequence of increasing numbers. 
If two sub-sequences have the same length, use the one that occurs first. 
An increasing sub-sequence must have a length of 2 or greater to qualify.
	
(= (__ [1 0 1 2 3 0 4 5]) [0 1 2 3])
	
(= (__ [5 6 1 3 2 7]) [5 6])
	
(= (__ [2 3 3 4 5]) [3 4 5])
	
(= (__ [7 6 5 4]) [])

*)
let increasesubseq l = 
    let rec increasesubseqinner l intermediateresult accuresult =
        match (l,intermediateresult,accuresult) with
        |([],[_],_) -> accuresult // when the intermediateresult contains only one item
        // cons the intermediateresult with the accuresult
        |([],_,_) ->  (intermediateresult::accuresult) 
        |(h::t,[],_) -> increasesubseqinner t [h] accuresult // first item in the list
        |(h::t,h1::_,_) -> 
            if h1+1 = h then increasesubseqinner t (h::intermediateresult) accuresult
            else increasesubseqinner t [h] (intermediateresult::accuresult)
        // when there is only 1 item 
        |(_::t,_::t1,_) when t1.IsEmpty ->  increasesubseqinner t [] accuresult 
        // when the accresult is [[]]
        |(_::t,_,h::_) when h.IsEmpty ->  increasesubseqinner t [] [intermediateresult] 
    let n = increasesubseqinner l [] [[]] 
            |> List.maxBy(fun x -> List.length(x))
            |> List.rev
    if n.Tail.IsEmpty then [] else n


increasesubseq [5;6;1;3;2;7] 
increasesubseq [1;0;1;2;3;0;4;5]
increasesubseq [2;3;3;4;5]
increasesubseq [7;6;5;4]

val increasesubseq : l:int list -> int list

Full name: Script.increasesubseq

val l : int list

val increasesubseqinner : (int list -> int list -> int list list -> int list list)

val intermediateresult : int list

val accuresult : int list list

val h : int

val t : int list

val h1 : int

val t1 : int list

property List.IsEmpty: bool

val h : int list

val n : int list

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val maxBy : projection:('T -> 'U) -> list:'T list -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.List.maxBy

val x : int list

val length : list:'T list -> int

Full name: Microsoft.FSharp.Collections.List.length

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

property List.Tail: int list

Raw view Test code New version

More information

Link:	http://fssnip.net/8v
Posted:	13 years ago
Author:	Naveen
Tags:	puzzle