Pagini recente » Cod sursa (job #3126860) | Cod sursa (job #1721952) | Cod sursa (job #2486581) | Cod sursa (job #61484) | Cod sursa (job #2127816)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
private static int[] array;
private static int N;
private static Stack<Integer> subsequence = new Stack<>();
public static void main(String[] args) {
MyScanner sc = new MyScanner("scmax.in", "scmax.out");
N = sc.nextInt();
array = new int[N];
for (int i = 0; i < N; i++) {
array[i] = sc.nextInt();
}
int max = subsirCrescatorMaximal();
StringBuilder sb = new StringBuilder();
while (!subsequence.empty()) {
sb.append(String.valueOf(subsequence.pop()));
sb.append(" ");
}
try {
sc.bw.write(String.valueOf(max));
sc.bw.newLine();
sc.bw.write(sb.toString());
} catch (IOException e) {
e.printStackTrace();
}
sc.close();
}
private static int maxIndex(int[] els, int endIndex) {
int max = -1;
int index = -1;
for (int i = endIndex; i >= 0; i--) {
if (els[i] > max) {
max = els[i];
index = i;
}
}
return index;
}
private static int subsirCrescatorMaximal() {
int[] best = new int[N];
int[] predecesor = new int[N];
best[0] = 1;
predecesor[0] = -1;
int maxBest;
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;
}
int indexOfMax = maxIndex(best, N-1);
int index = indexOfMax;
subsequence.push(array[index]);
while (predecesor[index] >= 0) {
subsequence.push(array[predecesor[index]]);
index = predecesor[index];
}
return best[indexOfMax];
}
}
class MyScanner {
BufferedWriter bw;
BufferedReader br;
StringTokenizer st;
public MyScanner() {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
}
public MyScanner(String in, String out) {
try {
br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(in))));
bw = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(new File(out))));
} catch (FileNotFoundException e) {
e.printStackTrace();
}
}
void close() {
try {
br.close();
bw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine(){
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}