public class PisinKetju {
    public static void main(String[] args) {
        int[] luvut = {3, 2, 8, 5, 3, 4, 1, 9};
        int[] pisin = new int[luvut.length];
        int[] vanha = new int[luvut.length];
        int pituus = 0, vika = 0;
        for (int i = 0; i < luvut.length; i++) {
            pisin[i] = 1;
            for (int j = 0; j < i; j++) {
                if (luvut[j] >= luvut[i]) continue;
                if (pisin[j]+1 <= pisin[i]) continue;
                pisin[i] = pisin[j]+1;
                vanha[i] = j;
            }
            if (pisin[i] > pituus) {
                pituus = pisin[i];
                vika = i;
            }
        }
        int[] ketju = new int[pituus];
        int kohta = vika;
        for (int i = pituus-1; i >= 0; i--) {
            ketju[i] = luvut[kohta];
            kohta = vanha[kohta];
        }
        for (int i = 0; i < pituus; i++) {
            System.out.print(ketju[i] + " ");
        }
        System.out.println();
    }
}