segmenty fib

let exampletab = [|4;2;1;2;3;5;2;8;7|]
let ex2 = [|5;8;13;21|]
(* znajdz maksa w tablicy *)
let m tab =
        let top = ref 0 in
        let len = Array.length tab in
        begin
                for i = 0 to len - 1 do
                        if tab.(i) > !top then top := tab.(i);
                done;
        end;!top

(* zmapuj elementy tablicy na ich indeks w ciagu fib, -1 w przeciwnym przypadku
 * 1 moze miec wartosci 1 lub 2, ale dostaje tutaj 2 *)
let rzad tab maxi =
        let h = Hashtbl.create 0 in
        let len = Array.length tab in
        let a = ref 1 in
        let b = ref 1 in
        let i = ref 1 in
        begin
                while !a <= maxi do
                        Hashtbl.add h !a !i;
                        b := !b + !a;
                        a := !b - !a;
                        i := !i + 1;
                done;
                for i = 0 to len - 1 do
                        match Hashtbl.find_opt h tab.(i) with
                        | None -> tab.(i) <- (-1)
                        | Some x -> tab.(i) <- x
                done;
        end;
        tab

(* laczy dwa segmenty fib o rzedach a,b i zwraca wartosc tego segmentu polaczanego
 * obsluguje przypadek kiedy a=2 i b=2 (bo mamy wtedy dwie jedynki obok siebie czyli mozna zrobic z tego segment mocy 3) *)
let polaczrzedy a b =
        if (a<0) || (b<0) then (-1)
        else if (a = 2) && (b = 2) then 3
        else if a = (b+1) then (a+1)
        else if b = (a+1) then (b+1)
        else (-1)

let segment tab =
        let maxi = m tab in
        let rzadtab = rzad tab maxi in
        let len = Array.length tab in
        let dp = Array.make_matrix len len (-1) in
        let max_wynik = ref (-1) in
        let rembmax = ref (-1) in
        begin
                (* wypelnianie przekatnej *)
                for i = 0 to len - 1 do
                        dp.(i).(i) <- rzadtab.(i);
                        max_wynik := max !max_wynik rzadtab.(i);
                done;
                (* wypelnianie reszty tablicy dp od dolu po kolejnych wierszach *)
                (* wybranie wiersza *)
                for i = len - 2 downto 0 do
                        (* wybierz komorki w wierszu do wypelnienia *)
                        for j = i + 1 to len - 1 do
                                rembmax := (-1);
                                (* wybierz maksa z wszystkich mozliwych kombinacji *)
                                for k = i to j-1 do
                                        rembmax := max !rembmax (polaczrzedy (dp.(i).(k)) (dp.(k+1).(j)))
                                done;
                                dp.(i).(j) <- !rembmax;
                                max_wynik := max !max_wynik !rembmax;
                        done;
                done;
        end;!max_wynik