Riešenia (skupina D, 7. týždeň)

import java.util.Arrays;

public class Postupnost {

        public static void main(String[] args) {
                int[] postupnost = new int[] { 8, 5, 3, 2, 8, 6, 4, 7, 1, 9, 4 };
                int[] d = new int[postupnost.length];

                d[0] = 1;
                for (int i = 1; i < d.length; i++) {
                        // minimalna podpostupnost je dlzky 1, preto 0
                        int max = 0;
                        for (int j = 0; j < i; j++) {
                                if (postupnost[i] > postupnost[j]) {
                                        max = Math.max(max, d[j]);
                                }
                        }
                        // tu je vysvetlenie predoslej poznamky
                        d[i] = max + 1;
                }

                System.out.println(Arrays.toString(d));

                // vysledok je maximum
                int celkoveMax = -1;
                for (int i = 0; i < d.length; i++) {
                        if (d[i] > celkoveMax) {
                                celkoveMax = d[i];
                        }
                }
                if (celkoveMax == 1) {
                        System.out.println("ja to nepovazujem za rastucu podpostupnost");
                } else {
                        System.out.println(celkoveMax);
                }

        }

}
 

public class Vyplatenie {
        public static void main(String[] args) {
                int suma = 35;
                int[] bankovky = new int[] { 20, 10, 2, 2, 1 };

                boolean[][] d = new boolean[suma + 1][bankovky.length];

                d[0][0] = true;
                d[bankovky[0]][0] = true;
                for (int riadok = 0; riadok < d.length; riadok++) {
                        for (int stlpec = 1; stlpec < d[0].length; stlpec++) {
                                if (riadok - bankovky[stlpec] >= 0) {
                                        d[riadok][stlpec] = d[riadok - bankovky[stlpec]][stlpec - 1];
                                }
                        }
                }

                // pre sumu 35 by malo byt true
                System.out.println(d[suma][bankovky.length - 1]);
                // pre sumu 7 by malo byt false
                System.out.println(d[7][bankovky.length - 1]);

        }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class ZahradkarskaUloha {

        public static int zahradka(int[][] zahrada, List<Character> cesta) {
                int vyska = zahrada.length, sirka = zahrada[0].length;
                int[][] pole = new int[vyska + 1][sirka + 1];

                for (int x = 1; x < vyska + 1; x++) {
                        for (int y = 1; y < sirka + 1; y++) {
//                              pole[x][y] = zahrada[x - 1][y - 1];
                                pole[x][y] = zahrada[x - 1][y - 1] + Math.max(pole[x - 1][y], pole[x][y - 1]);
                        }
                }

                if (cesta == null)
                        return pole[vyska][sirka];

                // cesta.clear();
                int y = vyska, x = sirka;
                while (!(y == 1 && x == 1)) {
                        if (pole[y - 1][x] > pole[y][x - 1]) {
                                cesta.add('D');
                                y--;
                        } else {
                                cesta.add('P');
                                x--;
                        }
                }
                Collections.reverse(cesta);

                return pole[vyska][sirka];
        }

        // public static int zahradka(int[][] zahrada, List<Character> cesta) {
        //
        // }

        public static void main(String[] args) {
                // System.out.println(jeZaplatitelna(250, new int[] { 100, 100, 200, 10,
                // 10, 10, 500, 5, 5 }));

                int[][] zahrada = new int[][] { { 3, 1, 4, 3, 1, 2 },
                                                                                { 4, 1, 2, 3, 4, 1 },
                                                                                { 8, 4, 2, 3, 4, 2},
                                                                                { 1, 2, 3, 8, 9, 1},
                /* { 5, 6, 8, 6, 8 }, */
                };
                List<Character> cesta = new ArrayList<Character>();
                System.out.println(zahradka(zahrada, cesta));
                 System.out.println(cesta);
        }
}