F# on Algorithms - Longest Increasing Sequence (LIS)

The Longest Increasing Sequence (LIS). The approach is to use a DP array to hold the current LIS till this index. For example, if the value in DP.[10] is 3 means the LIS for array.[0..9] is 3. The DP.[i]'s value is updated only when the new value (DP.[j] + 1) is better than current value (DP.[i] < DP.[j] + 1) and the value is still increasing (array.[i] > array.[j]).

The code is listed below.

let list = [|10; 22; 9; 33; 21; 50; 41; 60; 80|]
let DP = Array.create list.Length 1

let findMax () =
    let mutable maxLength = 1
    for i=1 to list.Length - 1 do
        for j=i-1 downto 0 do
            if list.[i] > list.[j] &&
               DP.[i] < DP.[j] + 1 then
               DP.[i] <- DP.[j] + 1

        maxLength <- max maxLength DP.[i]

    maxLength

findMax()