Pagini recente » Cod sursa (job #2699619) | Cod sursa (job #3266370)
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void print(PrintStream ps, int[] a, int[] pred, int last) {
if (pred[last] != -1) print(ps, a, pred, pred[last]);
ps.print(a[last] + " ");
}
public static void main(String[] args) throws IOException {
try (BufferedReader reader = new BufferedReader(new FileReader("scmax.in"));
PrintStream ps = new PrintStream(new FileOutputStream("scmax.out"), true)) {
StringTokenizer st = new StringTokenizer(reader.readLine());
int N = Integer.parseInt(st.nextToken());
int[] a = new int[N+1];
st = new StringTokenizer(reader.readLine());
for (int i = 1; i <= N; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
int[] dp = new int[N+1];
int[] pred = new int[N+1];
Arrays.fill(pred, -1);
int max = 1;
int last = 1;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = 1;
for (int j = 1; j < i; j++) {
if (a[i] > a[j] && dp[i] < dp[j] + 1) {
dp[i] = 1 + dp[j];
pred[i] = j;
if (dp[i] > max) {
max = dp[i];
last = i;
}
}
}
}
ps.println(max);
print(ps, a, pred, last);
}
}
}