Pagini recente » Cod sursa (job #2970249) | Cod sursa (job #504337) | Cod sursa (job #224421) | Cod sursa (job #2738373) | Cod sursa (job #2127814)
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;
class SubsirCrescatorMaximal {
private static int[] array;// = new int[] {24, 12, 15, 15, 8, 19};
private static int N;// = 6;
private static Stack<Integer> subsequence = new Stack<>();
public static void main(String[] args) {
MyScanner sc = new MyScanner("scmax.in", "scmax.out");
// System.out.println("Enter array length");
N = sc.nextInt();
array = new int[N];
// System.out.println("Enter array elements");
for (int i = 0; i < N; i++) {
array[i] = sc.nextInt();
}
/*System.out.print("Array entered: { ");
for (int e : array) System.out.print(e + " ");
System.out.println("}");
System.out.println("Max Ascending Subsequence: " + subsirCrescatorMaximal());*/
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;
}
/*System.out.print("Element - best - predecesor:\n");
for (int i = 0; i < N; i++) {
System.out.println(array[i] + " - " + best[i] + " - " + predecesor[i]);
}*/
int indexOfMax = maxIndex(best, N-1);
int index = indexOfMax;
//System.out.print("The maximum ascending subsequence is: { ");
//System.out.print(array[index] + " ");
subsequence.push(array[index]);
while (predecesor[index] >= 0) {
//System.out.print(array[predecesor[index]] + " ");
subsequence.push(array[predecesor[index]]);
index = predecesor[index];
}
// System.out.println("}");
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;
}
}