Longest Consecutive Sequence In a Sequence of Ints

longestConsecutiveSequenece.fsx

//Given an unsorted array of integers, return the length of ther longest
//consecutive elements sequence where the integers
//in the sequence are in inremental order.

//eg: [2,1,2,6,4,5,1,7] -> [1,2,4,5,7]

open System

type Token = {Index: int; Number:int}

let rec getNextNumbers (lastToken:Token) (remainingTokens: Token list) (foundTokens: Token list)=
    let filteredTokens =
        remainingTokens 
        |> Seq.filter(fun rt -> rt.Number > lastToken.Number)
    let found =
        match filteredTokens |> Seq.length with
        | 0 -> None
        | _ -> Some (filteredTokens |> Seq.head)
    match found with
    | None -> foundTokens
    | Some ft -> 
        let updateFoundTokens = Seq.append foundTokens [ft] |> Seq.toList
        let startingIndex = ft.Index
        let updatedRemainingTokens = remainingTokens.[startingIndex..]
        getNextNumbers ft updatedRemainingTokens updateFoundTokens

// let token0 = {Index=0;Number=1}
// let token1 = {Index=1;Number=3}
// let token2 = {Index=2;Number=2}
// let remianingTokens = [token0;token1;token2]
// let foundTokens = List.empty<Token>

// getNextNumbers token0 remianingTokens foundTokens

let getAllGoodNumbers (token:Token) (allTokens: Token list ) =
    let token0 = allTokens |> Seq.head
    let remainingTokens = allTokens.[1..]
    let foundTokens = List.empty<Token>
    getNextNumbers token0 remainingTokens foundTokens

let getLongestSequence (allNumbers: int list) =
    match allNumbers.Length with
    | 0 -> []
    | 1 -> allNumbers
    | _ -> 
        let allTokens =
            allNumbers 
            |> Seq.mapi(fun idx n -> {Index=idx;Number=n})
            |> Seq.toList
        allTokens
        |> Seq.map(fun t -> getAllGoodNumbers t allTokens)
        |> Seq.map(fun tl -> tl.Length, tl)
        |> Seq.sortByDescending(fun (l, tl) -> l)
        |> Seq.map(fun (l, tl) -> tl)
        |> Seq.head
        |> Seq.map(fun tl -> tl.Number)
        |> Seq.toList

//[] -> []
//[2] -> 2
//[2;1] -> []
//[2;1;2] -> [1;2]
//[2;1;2;6] -> [2;6] & [1;2;6]
//[2;1;2;6;4] -> [2;6] & [2;4] & [1;2;6] & [1;2;4] & [2;6] & [2;4]
//[2;1;2;6;4;5] -> [2;6] & [2;4;5] & [1;2;6] & [1;2;4;5]
//[2;1;2;6;4;5;1] -> [2;6] & [2;4;5] & [1;2;6] & [1;2;4;5]
//[2;1;2;6;4;5;1;7] -> [2;6;7] & [2;4;5;7] & [1;2;6;7] & [1;2;4;5] & [1;2;4;5;7]