Cod sursa(job #3266370)

Utilizator lucky1992Ion Ion lucky1992 Data 7 ianuarie 2025 20:18:20
Problema Subsir crescator maximal Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 1.31 kb
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

  public static void print(PrintStream ps, int[] a, int[] pred, int last) {
    if (pred[last] != -1) print(ps, a, pred, pred[last]);
    ps.print(a[last] + " ");
  }

  public static void main(String[] args) throws IOException {
    try (BufferedReader reader = new BufferedReader(new FileReader("scmax.in"));
         PrintStream ps = new PrintStream(new FileOutputStream("scmax.out"), true)) {

      StringTokenizer st = new StringTokenizer(reader.readLine());

      int N = Integer.parseInt(st.nextToken());
      int[] a = new int[N+1];

      st = new StringTokenizer(reader.readLine());

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

      int[] dp = new int[N+1];
      int[] pred = new int[N+1];

      Arrays.fill(pred, -1);

      int max = 1;
      int last = 1;

      dp[1] = 1;

      for (int i = 2; i <= N; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++) {
          if (a[i] > a[j] && dp[i] < dp[j] + 1) {
            dp[i] = 1 + dp[j];
            pred[i] = j;
            if (dp[i] > max) {
              max = dp[i];
              last = i;
            }
          }
        }
      }

      ps.println(max);
      print(ps, a, pred, last);
    }
  }
}