Pagini recente » Cod sursa (job #551165) | Cod sursa (job #411600) | Cod sursa (job #1815810) | Cod sursa (job #1864322) | Cod sursa (job #2127821)
import java.io.File;
import java.io.FileWriter;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
try {
Scanner sc = new Scanner(new File("scmax.in"));
int N = sc.nextInt();
int[] array = new int[N];
for (int i = 0; i < N; i++)
array[i] = sc.nextInt();
sc.close();
int[] best = new int[N];
int[] predecesor = new int[N];
best[0] = 1;
predecesor[0] = -1;
int maxBest, globalBest = 0, endIndex = -1;
for (int i = 1; i < N; i++) {
predecesor[i] = -1;
maxBest = 0;
for (int j = i - 1; j >= 0; j--) {
if (array[i] > array[j])
if (best[j] > maxBest) {
maxBest = best[j];
predecesor[i] = j;
}
}
best[i] = 1 + maxBest;
if (best[i] > globalBest) {
globalBest = best[i];
endIndex = i;
}
}
Stack<Integer> subsequence = new Stack<>();
int index = endIndex;
subsequence.push(array[index]);
while (predecesor[index] >= 0) {
subsequence.push(array[predecesor[index]]);
index = predecesor[index];
}
FileWriter fw = new FileWriter("scmax.out");
fw.write(String.valueOf(globalBest) + "\n");
fw.write(String.valueOf(subsequence.pop()));
while (!subsequence.empty()) {
fw.write(" " + String.valueOf(subsequence.pop()));
}
fw.flush();
fw.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}