## Tuesday, May 1, 2012

### A fast solution for Dynamic Programming.

This idea and source come from USACO Training article.
```import java.io.BufferedReader;

//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 {
long[] number = new long[N];
for (int i = 0; i < N; i++)
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
* */
```