A7

package cvB07.cvB07;

import java.util.Arrays;

public class Pokusy {
        public static int pocitadlo = 0;
        public static int[] pomocnePole;

        public static int fibonacci2(int n) {
                pocitadlo++;
                if (n <= 1)
                        return n;
                else
                        return fibonacci2(n - 1) + fibonacci2(n - 2);
        }

        // startovacia metoda
        public static int fibonacci(int n) {
                pomocnePole = new int[n + 1];
                Arrays.fill(pomocnePole, -1);
                pomocnePole[0] = 0;
                pomocnePole[1] = 1;
                return fibonacciDymanicky(n);
        }

        public static int fibonacciSMemoizaciou(int n) {
                // ak pomocne pole obsahuje prvok, ktory potrebujem,
                // vyuzijem ho
                if (pomocnePole[n] != -1)
                        return pomocnePole[n];
                // ak pomocne pole neobsahuje prvok, ktory potrebujem
                // vypocitam ho
                if (n >= 2) {
                        pomocnePole[n] = fibonacciSMemoizaciou(n - 1) + fibonacciSMemoizaciou(n - 2);
                }
                return pomocnePole[n];
        }

        public static int fibonacciDymanicky(int n) {
                // vypocitame cele pomocne pole naraz
                for (int i = 2; i < pomocnePole.length; i++) {
                        pomocnePole[i] = pomocnePole[i - 1] + pomocnePole[i - 2];
                }
                return pomocnePole[n];
        }

        public static void main(String[] args) {
                System.out.println(fibonacci(5));
                System.out.println(Arrays.toString(pomocnePole));
                // System.out.println("Pocitadlo je: " + pocitadlo);
        }

}
 

package cvB07.cvB07;

import java.util.ArrayList;
import java.util.Arrays;

public class NVRP {
        private int[] postupnost;
        private int[] dlzky;

        private int indexMaxima;

        public NVRP(int[] postupnost) {
                this.postupnost = postupnost.clone();
                this.dlzky = new int[postupnost.length];
        }

        //vrati dlzku najdlhsej vybranej rastucej podpostupnosti
        public int najdiDlzkuNajdlhsej() {
                // predpripravime si pole dlzok hodnotou 1, na kazdom indexe bude urcite aspon
                // hodnota 1
                Arrays.fill(dlzky, 1);
                // vyplnime pole dlzok
                for (int i = 0; i < postupnost.length; i++) {
                        for (int j = 0; j < i; j++) {
                                if (postupnost[j] < postupnost[i])
                                        dlzky[i] = Math.max(dlzky[i], dlzky[j] + 1);
                        }
                }
                // najdeme vysledok - maximum v poli
                int maximum = 0;
                for (int i = 0; i < dlzky.length; i++) {
                        if (maximum < dlzky[i]) {
                                maximum = dlzky[i];
                                indexMaxima = i;
                        }
                }
                return maximum;
        }

        // vrati najdlhsiu vybranu rastucu podpostupnost pomocou spatneho prechodu
        public int[] najdiNajdlhsiu() {
                najdiDlzkuNajdlhsej();
                // zacneme hladat najvacsi prvok postupnosti
                int maximalnaDlzka = dlzky[indexMaxima];
                int[] najdlhsiaPodpostupnost = new int[maximalnaDlzka];
                // prejdeme cele pole dlzok a postupne hladame od najvacsieho po najmensi prvok
                // vybranej postupnosti
                // tak, ze zmensujeme hladanu dlzku a prislusny prvok z postupnosti vlozime na
                // jeho miesto vo vybranej pospostupnosti
                for (int i = dlzky.length - 1; i >= 0; i--) {
                        if (dlzky[i] == maximalnaDlzka) {
                                najdlhsiaPodpostupnost[maximalnaDlzka - 1] = postupnost[i];
                                maximalnaDlzka--;
                        }
                }
                return najdlhsiaPodpostupnost;
        }

        // vrati najdlhsiu vybranu rastucu podpostupnost bez spatneho prechodu
        public int[] najdiNajdlhsiuPodpostupnost() {
                // predpripravime si pole dlzok hodnotou 1, na kazdom indexe bude urcite aspon
                // hodnota 1
                Arrays.fill(dlzky, 1);
                // pole na zapamatanie odkial prvok ziskal aktualnu dlzku podpostupnosti v nom
                // konciacej
                int[] cache = new int[postupnost.length];
                Arrays.fill(cache, -1);
                // vyplnime pole dlzok a sucasne pomocnu pamat
                for (int i = 0; i < postupnost.length; i++) {
                        for (int j = 0; j < i; j++) {
                                if (postupnost[j] <= postupnost[i]) {
                                        if (dlzky[j] + 1 > dlzky[i]) {
                                                dlzky[i] = dlzky[j] + 1;
                                                cache[i] = j;
                                        } else {
                                                dlzky[i] = dlzky[i];
                                        }
                                }
                                if (dlzky[i] > dlzky[indexMaxima])
                                        indexMaxima = i;
                        }
                }
                System.out.println("postupnost:" + Arrays.toString(postupnost));
                System.out.println("dlzky: " + Arrays.toString(dlzky));
                System.out.println("cache: " + Arrays.toString(cache));

                // skontruujeme vyslednu podpostupnost pomocou pomocneho pola
                int[] podpostupnost = new int[dlzky[indexMaxima]];
                Arrays.fill(podpostupnost, -1);
                int id = 0;
                int lastI = 0;
                for (int i = 0; i < cache.length; i++) {
                        // specialne pridame prvy prvok postupnosti
                        if (cache[i] != -1 && id == 0) {
                                podpostupnost[id] = postupnost[cache[i]];
                                id++;
                                lastI = i;
                        } else if (cache[i] == lastI) {
                                // kazdy nasledujuci pridame porovnanim posledneho indexu a aktualnej hodnoty
                                // pola
                                podpostupnost[id] = postupnost[cache[i]];
                                id++;
                                lastI = i;
                        }
                }
                // specialne pridame posledny prvok postupnosti
                if (id == dlzky[indexMaxima] - 1 && podpostupnost[id] == -1) {
                        podpostupnost[id] = postupnost[lastI];
                }
                return podpostupnost;
        }

        public static void main(String[] args) {
                int[] postupnost = { 4, 2, 9, 1, 11, 3, 7, 14, 3, 15, 7 };
                System.out.println(Arrays.toString(postupnost));
                NVRP nvrp = new NVRP(postupnost);
                System.out.println(nvrp.najdiDlzkuNajdlhsej());
                System.out.println(Arrays.toString(nvrp.najdiNajdlhsiu()));

                System.out.println(Arrays.toString(nvrp.najdiNajdlhsiuPodpostupnost()));
        }

}