Cod sursa(job #2127814)

Utilizator fylot3Bogdan Filote fylot3 Data 11 februarie 2018 02:26:22
Problema Subsir crescator maximal Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 4.82 kb
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;
    }
}