A fast solution for Dynamic Programming.

This idea and source come from USACO Training article.

import java.io.BufferedReader;
import java.io.InputStreamReader;

//best[i]: i is the length of best subsequence, 
//best[i] is the smallest possible element while largest in this subsequence element.
//Amazing Dynamic Programming;

public class Main {

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        main.run();
        System.exit(0);
    }

    public void run() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] number = new long[N];
        for (int i = 0; i < N; i++)
            number[i] = Long.parseLong(br.readLine());
        long[] best = new long[N + 1];
        best[0] = number[N - 1];
        int bestsofar = 1;
        for (int i = N - 1 - 1; i >= 0; i--) {
            if (number[i] < best[0])
                best[0] = number[i];
            else {
                for (int j = bestsofar - 1; j >= 0; j--) {
                    if (best[j] < number[i])
                        if (j == bestsofar - 1 || best[j + 1] > number[i]) {
                            best[j + 1] = number[i];
                            if (j + 1 == bestsofar)
                                bestsofar++;
                            break;
                        }
                }
            }
        }
        System.out.println(bestsofar);
        for (int i = 0; i < bestsofar; i++)
            System.out.println(best[i]);
    }
}

/**
 * Test: 
 * 
 * 6 
 * 10 8 9 4 6 3
 * 
 * 4 
 * 3 4 8 10
 * */