Cod sursa(job #2127819)

Utilizator fylot3Bogdan Filote fylot3 Data 11 februarie 2018 03:08:09
Problema Subsir crescator maximal Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.08 kb
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();
        }
    }
}