let lps s =
  let n = String.length s in
  let dp = Array.init n (fun _ -> Array.make n 0) in
  for i = 0 to n - 1 do dp.(i).(i) <- 1 done;
  for len = 2 to n do
    for i = 0 to n - len do
      let j = i + len - 1 in
      if s.[i] = s.[j] then
        dp.(i).(j) <- (if len = 2 then 2 else dp.(i + 1).(j - 1) + 2)
      else begin
        let a = dp.(i + 1).(j) in
        let b = dp.(i).(j - 1) in
        dp.(i).(j) <- if a > b then a else b
      end
    done
  done;
  dp.(0).(n - 1)

;;

lps "BBABCBCAB"
