Cod sursa(job #3345492)

Utilizator teo_mariaa_Tecu Teodora teo_mariaa_ Data 9 martie 2026 19:41:59
Problema Subsir crescator maximal Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 1.52 kb
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new FileReader("scmax.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("scmax.out")));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] a = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        int poz = 1;
        int[] dp = new int[n + 1];
        int[] prev = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            dp[i] = 1;
            prev[i] = -1;
        }

        for (int i = 2; i <= n; i++) {
            for (int k = 1; k < i; k++) {
                if (a[k] < a[i]) {
                    if (dp[k] + 1 > dp[i]) {
                        dp[i] = dp[k] + 1;
                        prev[i] = k;
                    }
                }
            }
        }

        int Lmax = 0;

        for (int i = 1; i <= n; i++) {
            if (dp[i] > Lmax) {
                Lmax = dp[i];
                poz = i;
            }
        }

        out.println(Lmax);

        int[] sol = new int[Lmax];
        int index = Lmax - 1;

        for (int i = poz; i != -1; i = prev[i]) {
            sol[index--] = a[i];
        }

        for (int i = 0; i < Lmax; i++) {
            out.print(sol[i] + " ");
        }

        br.close();
        out.close();
    }
}