Cod sursa(job #3345904)

Utilizator andreiu037Vasile Stan andreiu037 Data 11 martie 2026 19:03:38
Problema Subsir crescator maximal Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.48 kb
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

public class Scmax {
    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(new File("scmax.in"));
            FileWriter outf = new FileWriter("scmax.out");
            int n = s.nextInt();
            int[] arr = new int[n];
            ArrayList<Integer>[] sols = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                arr[i] = s.nextInt();
                sols[i] = new ArrayList<>();
            }
            int[] dp = new int[n];
            dp[0] = 1;
            sols[0].add(arr[0]);
            for (int i = 1; i < n; i++) {
                dp[i] = 1;
                sols[i].add(arr[i]);
                for (int j = 0; j < i; j++) {
                    if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        sols[i].clear();
                        sols[i].addAll(sols[j]);
                        sols[i].add(arr[i]);
                    }
                }
            }
            int max = -1, ind = -1;
            for (int i = 0; i < n; i++)
                if (max < dp[i]) {
                    max = dp[i];
                    ind = i;
                }
            outf.append(max + "\n");
            for (int a : sols[ind])
                outf.append(a + " ");
            outf.close();
        } catch (IOException e) {

        }
    }

}