let max_profit_two prices =
  let n = Array.length prices in
  if n < 2 then 0
  else begin
    let left = Array.make n 0 in
    let min_p = ref prices.(0) in
    for i = 1 to n - 1 do
      if prices.(i) < !min_p then min_p := prices.(i);
      let p = prices.(i) - !min_p in
      left.(i) <- if p > left.(i - 1) then p else left.(i - 1)
    done;
    let right = Array.make n 0 in
    let max_p = ref prices.(n - 1) in
    for i = n - 2 downto 0 do
      if prices.(i) > !max_p then max_p := prices.(i);
      let p = !max_p - prices.(i) in
      right.(i) <- if p > right.(i + 1) then p else right.(i + 1)
    done;
    let best = ref 0 in
    for i = 0 to n - 1 do
      let total = left.(i) + right.(i) in
      if total > !best then best := total
    done;
    !best
  end

;;

max_profit_two [| 3; 3; 5; 0; 0; 3; 1; 4 |]
