Thursday, October 4, 2012
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. 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]