package PAZ1b.cvicenie07;

import java.util.Arrays;

import sk.upjs.jpaz2.*;

public class Launcher {

        public static int dlzkaNajdlhsejVybranejRastucejPodpostupnosti(int[] pole) {
                int[] akaJeDlzkaNVRPnaIdxI = new int[pole.length];
                // prechadzam vsetkymi indexami pola
                for (int i = 0; i < pole.length; i++) {

                        akaJeDlzkaNVRPnaIdxI[i] = 1;
                        for (int j = 0; j < i; j++) {
                                if (pole[i] > pole[j] && akaJeDlzkaNVRPnaIdxI[j] + 1 > akaJeDlzkaNVRPnaIdxI[i]) {
                                        akaJeDlzkaNVRPnaIdxI[i] = akaJeDlzkaNVRPnaIdxI[j] + 1;
                                }
                        }
                }
                System.out.println(Arrays.toString(pole));
                System.out.println(Arrays.toString(akaJeDlzkaNVRPnaIdxI));

                return 0;
        }

        public static void main(String[] args) {
                int[] pole = { 3, 2, 93, 1, 2, 3, 100, 7, 8, 97, 9, 10, -1 };
                dlzkaNajdlhsejVybranejRastucejPodpostupnosti(pole);

        }
}

package PAZ1b.cvicenie07;

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

import sk.upjs.jpaz2.*;

public class Launcher {

        public static int dlzkaNajdlhsejVybranejRastucejPodpostupnosti(int[] pole) {
                int[] akaJeDlzkaNVRPnaIdxI = new int[pole.length];
                // prechadzam vsetkymi indexami pola
                for (int i = 0; i < pole.length; i++) {

                        akaJeDlzkaNVRPnaIdxI[i] = 1;
                        for (int j = 0; j < i; j++) {
                                if (pole[i] > pole[j] && akaJeDlzkaNVRPnaIdxI[j] + 1 > akaJeDlzkaNVRPnaIdxI[i]) {
                                        akaJeDlzkaNVRPnaIdxI[i] = akaJeDlzkaNVRPnaIdxI[j] + 1;
                                }
                        }
                }
                System.out.println(Arrays.toString(pole));
                System.out.println(Arrays.toString(akaJeDlzkaNVRPnaIdxI));

                int idxMax = 0;
                for (int i = 1; i < akaJeDlzkaNVRPnaIdxI.length; i++) {
                        if (akaJeDlzkaNVRPnaIdxI[i] > akaJeDlzkaNVRPnaIdxI[idxMax]) {
                                idxMax = i;
                        }
                }
                System.out.println("dlzka najdlhsje vybranej rastucej podpostupnosti je: " + akaJeDlzkaNVRPnaIdxI[idxMax]);

                int idxPoslednejVypisanejHodnoty = idxMax;
                ArrayList<Integer> NVRP = new ArrayList<>();
                NVRP.add(pole[idxPoslednejVypisanejHodnoty]);

                for (int i = idxPoslednejVypisanejHodnoty - 1; i >= 0; i--) {
                        if (akaJeDlzkaNVRPnaIdxI[i] == akaJeDlzkaNVRPnaIdxI[idxPoslednejVypisanejHodnoty] - 1
                                        && pole[i] < pole[idxPoslednejVypisanejHodnoty]) {
                                NVRP.add(pole[i]);
                                idxPoslednejVypisanejHodnoty = i;
                        }
                }
                Collections.sort(NVRP);
                System.out.println(NVRP);

                return 0;
        }

        public static void zaplatenie(int[] bankovky) {
                int suma = 0;
                for (int i = 0; i < bankovky.length; i++) {
                        suma += bankovky[i];
                }

                boolean[][] viem = new boolean[bankovky.length + 1][suma + 1];
                viem[0][0] = true;

                for (int i = 1; i < bankovky.length + 1; i++) {
                        for (int j = 0; j <= suma; j++) {
                                System.out.println(i + " " + j);
                                if (viem[i - 1][j]) {
                                        viem[i][j] = viem[i - 1][j];
                                        viem[i][j + bankovky[i - 1]] = true;
                                }
                        }
                }

                for (int i = 0; i < viem.length; i++) {
                        System.out.println(Arrays.toString(viem[i]));
                }
        }

        public static void main(String[] args) {
//              int[] pole = { 3, 2, 93, 1, 2, 3, 100, 8, 7, 97, 9, 10, -3 };
//              dlzkaNajdlhsejVybranejRastucejPodpostupnosti(pole);

                int[] bankovky = { 2, 2, 3, 3, 2 };
                zaplatenie(bankovky);
        }
}

package PAZ1b.cvicenie07;

public class AttilovaZahrada {

        public static void maxPocJablk(int[][] zahrada) {
                int[][] novePole = new int[zahrada.length][zahrada[0].length];
                novePole[0][0] = zahrada[0][0];

                for (int i = 1; i < novePole.length; i++) {
                        novePole[i][0] = zahrada[i][0] + novePole[i - 1][0];
                }
                for (int i = 1; i < novePole[0].length; i++) {
                        novePole[0][i] = zahrada[0][i] + novePole[0][i - 1];
                }
                for (int i = 1; i < novePole.length; i++) {
                        for (int j = 1; j < novePole[0].length; j++) {
                                novePole[i][j] = Math.max(novePole[i-1][j], novePole[i][j-1]) + zahrada[i][j];
                        }
                }
                vypis2Dpole(novePole);
        }

        public static void vypis2Dpole(int[][] pole) {
                for (int i = 0; i < pole.length; i++) {
                        for (int j = 0; j < pole[0].length; j++) {
                                System.out.print(pole[i][j] + "\t");
                        }
                        System.out.println();
                }
        }

        public static void main(String[] args) {
                int[][] zahrada = { { 7, 10, 9, 2, 10 }, { 13, 2, 1, 3, 1 }, { 4, 4, 9, 3, 2 }, { 13, 0, 1, 1, 8 } };
                maxPocJablk(zahrada);
        }
}
 

package PAZ1b.cvicenie07;

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

public class AttilovaZahrada {

        public static void maxPocJablk(int[][] zahrada) {
                int[][] novePole = new int[zahrada.length][zahrada[0].length];
                novePole[0][0] = zahrada[0][0];

                for (int i = 1; i < novePole.length; i++) {
                        novePole[i][0] = zahrada[i][0] + novePole[i - 1][0];
                }
                for (int i = 1; i < novePole[0].length; i++) {
                        novePole[0][i] = zahrada[0][i] + novePole[0][i - 1];
                }
                for (int i = 1; i < novePole.length; i++) {
                        for (int j = 1; j < novePole[0].length; j++) {
                                novePole[i][j] = Math.max(novePole[i - 1][j], novePole[i][j - 1]) + zahrada[i][j];
                        }
                }
                vypis2Dpole(novePole);

                vypisCestu(novePole);
        }

        public static void vypisCestu(int[][] dp) {
                ArrayList<String> cesta = new ArrayList<>();

                int xAkt = dp.length - 1;
                int yAkt = dp[0].length - 1;
                while (xAkt > 0 || yAkt > 0) {

                        if (yAkt - 1 < 0) {
                                cesta.add("dole");
                                xAkt--;
                                continue;
                        }
                        if (xAkt - 1 < 0) {
                                cesta.add("vpravo");
                                yAkt--;
                                continue;
                        }

                        if (dp[xAkt][yAkt - 1] > dp[xAkt - 1][yAkt]) {
                                cesta.add("vpravo");
                                yAkt--;
                        } else {
                                cesta.add("dole");
                                xAkt--;
                        }
                }              
                Collections.reverse(cesta);
                System.out.println(cesta);

        }

        public static void vypis2Dpole(int[][] pole) {
                for (int i = 0; i < pole.length; i++) {
                        for (int j = 0; j < pole[0].length; j++) {
                                System.out.print(pole[i][j] + "\t");
                        }
                        System.out.println();
                }
        }

        public static void main(String[] args) {
                int[][] zahrada = { { 7, 10, 9, 2, 10 }, { 13, 2, 1, 3, 1 }, { 4, 4, 9, 3, 2 }, { 13, 0, 1, 1, 8 } };
                maxPocJablk(zahrada);
        }
}