C7

import java.util.Arrays;


public class NajdlhsiaVybranaPodpostupnost {

        int[] postupnost;
        int[] pole;
        int[] sipky;

        public NajdlhsiaVybranaPodpostupnost(int[] postupnost) {
                this.postupnost = postupnost;
                pole = new int[postupnost.length];
                sipky = new int[postupnost.length];
        }

        public void vyplnPole() {
                for (int i = 0; i < pole.length; i++) {
                        pole[i] = 1;
                        sipky[i] = -1;
                        for (int j = 0; j < i; j++) {
                                if (postupnost[i] > postupnost[j]) {
                                        if (pole[j] + 1 > pole[i]) {
                                                sipky[i] = j;
                                        }
                                        pole[i] = Math.max(pole[i], pole[j] + 1);
                                }
                        }
                }
                System.out.println(Arrays.toString(pole));
                System.out.println(Arrays.toString(sipky));
        }

        public void vypisVysledok() {
                int idx = 0;
                for (int i = 0; i < pole.length; i++) {
                        if (pole[i] > pole[idx]) {
                                idx = i;
                        }
                }

                int[] vysledok = new int[pole[idx]];
                for (int i = vysledok.length - 1; i > -1; i--) {
                        vysledok[i] = postupnost[idx];
                        idx = sipky[idx];
                }
                System.out.println(Arrays.toString(vysledok));
        }

        public static void main(String[] args) {
                int[] postupnost = new int[] {1,0,2,1,4,3,5,7,2};
                NajdlhsiaVybranaPodpostupnost p = new NajdlhsiaVybranaPodpostupnost(postupnost);
                p.vyplnPole();
                p.vypisVysledok();
        }

}

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

public class ZaplatenieNakupu {

        boolean[][] f;
        int[][] sipky;
        int[] bankovky;
        int suma;

        public ZaplatenieNakupu(int[] bankovky, int suma) {
                this.bankovky = bankovky;
                this.suma = suma;
                f = new boolean[bankovky.length + 1][suma + 1];
                sipky = new int[bankovky.length + 1][suma + 1];
        }

        public int viemeVyplatit(int i, int j) {
                if (j - bankovky[i - 1] < 0)
                        return -1;
                for (int i2 = 0; i2 < i; i2++) {
                        if (f[i2][j - bankovky[i - 1]])
                                return i2;
                }
                return -1;
        }

        public void vypocitaj() {
                for (int i = 0; i < f.length; i++) {
                        for (int j = 0; j < f[0].length; j++) {
                                f[i][j] = false;
                                sipky[i][j] = -1;
                        }
                }
                f[0][0] = true;
                for (int i = 1; i < f.length; i++) {
                        for (int j = 1; j < f[0].length; j++) {
                                int i2 = viemeVyplatit(i, j);
                                if (i2 != -1) {
                                        f[i][j] = true;
                                        sipky[i][j] = i2;
                                }
                        }
                }
        }

        public void rekonstrukcia() {
                ArrayList<Integer> peniaze = new ArrayList<Integer>();
                int index = 0;
                for (int i = 0; i < f.length; i++) {
                        if (f[i][suma] == true) {
                                index = i;
                        }
                }
                while (index > 0) {
                        peniaze.add(bankovky[index - 1]);
                        suma = suma - bankovky[index - 1];
                        index = sipky[index][suma + bankovky[index - 1]];
                }
                System.out.println(peniaze.toString());
        }

        public static void main(String[] args) {
                ZaplatenieNakupu zn = new ZaplatenieNakupu(new int[] { 1, 2, 2, 5, 5,
                                10, 20 }, 12);
                zn.vypocitaj();
                for (int i = 0; i < zn.f.length; i++) {
                        System.out.println(Arrays.toString(zn.f[i]));
                }

                System.out.println("Sipky");

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

import java.util.Arrays;


public class Zahrada {
        int[][] pocetJablk;
        int[][] maxPocetJablk;
        public Zahrada(int[][] pocetJablk){
                this.pocetJablk=pocetJablk;
                maxPocetJablk=new int[pocetJablk.length][pocetJablk[0].length];
        }

        public void vypocitaj(){
                for (int i = 0; i < pocetJablk.length; i++) {
                        for (int j = 0; j < pocetJablk[0].length; j++) {
                                maxPocetJablk[i][j]=Math.max((i==0) ? 0 : maxPocetJablk[i-1][j],
                                                                     (j==0) ? 0 : maxPocetJablk[i][j-1])
                                                                + pocetJablk[i][j];
                        }
                }
        }

        public void rekonstrukcia() {
                char[] prechod = new char[pocetJablk.length + pocetJablk[0].length - 2];
                int index = prechod.length - 1;
                int i = pocetJablk.length - 1;
                int j = pocetJablk[0].length - 1;
                while (i != 0 || j != 0) {
                        if (maxPocetJablk[i][j] == ((i==0) ? 0 : maxPocetJablk[i-1][j]) + pocetJablk[i][j]) {
                                prechod[index] = 'D';
                                i  = Math.max(0, i - 1);
                        } else {
                                prechod[index] = 'P';
                                j  = Math.max(0, j - 1);
                        }
                        index--;
                }
                System.out.println(prechod);
        }

        public static void main(String[] args) {
                int[][] pocetJablk= new int[][]{{10,5,100},{9,4,3},{1,8,2}};
                Zahrada z= new Zahrada(pocetJablk);
                z.vypocitaj();
                for (int i = 0; i < z.maxPocetJablk.length; i++) {
                        System.out.println(Arrays.toString(z.maxPocetJablk[i]));
                }
                z.rekonstrukcia();
        }
}

import java.util.Arrays;

public class LCS {

        int[][] pole;
        String a;
        String b;

        public LCS(String a, String b) {
                pole = new int[a.length() + 1][b.length() + 1];
                this.a = a;
                this.b = b;
        }

        public void vypocitaj() {
                for (int i = 0; i < pole[0].length; i++) {
                        pole[0][i] = 0;

                }
                for (int j = 0; j < pole.length; j++) {
                        pole[j][0] = 0;

                }
                for(int j= 1;j<pole.length;j++){
                        for(int i = 1 ;i<pole[0].length;i++){
                                pole[j][i]= Math.max(pole[j][i-1],pole[j-1][i] );
                                pole[j][i]= Math.max(pole[j][i],pole[j-1][i-1]+ (a.charAt(j-1)==b.charAt(i-1)? 1:0));
                        }

                }

        }
        public void vypis(){
                for(int j =0 ;j<pole.length;j++){
                        System.out.println(Arrays.toString(pole[j]));
                }
        }

        public void rekonstrukcia(){
                int i = b.length();
                int j = a.length();
                String vysledok = "";

                while(i!=0 && j!=0){
                        if(pole[j][i]==pole[j-1][i]){
                                j--;
                        }else if(pole[j][i]==pole[j][i-1]){
                                i--;
                        }else if(a.charAt(j-1)!=b.charAt(i-1)){
                                i--;j--;
                        }else{
                                vysledok=a.charAt(j-1)+vysledok;
                                i--;j--;
                        }

                }
                System.out.println(vysledok);

        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                LCS l = new LCS("abrcd","bcode");
                l.vypocitaj();
                l.vypis();
                l.rekonstrukcia();


        }

}