gistfile1.txt

import java.io.*;
import java.util.*;

public class Main {

       static final String FIN = "scmax.in";
       static final String FOUT = "scmax.out";
       static final int SIZE = 1000009;

       static int[] V = new int[SIZE];
       static int[] L = new int[SIZE];
       static int n;

       static void input() throws IOException {

              BufferedReader br = new BufferedReader(new FileReader(FIN));
              StreamTokenizer st = new StreamTokenizer(br);

              st.nextToken();

              n = (int) st.nval;

              for(int i  = 1; i <=n; ++i) {
                  st.nextToken();
                  V[i] = (int)st.nval;
              }

              br.close();
       }

       //     L[5] = 1
       /*
       5
       V =  21  12 15 15 19
       L = [ 1  2  2  2  1]
       //Complexitate TIME O(n^2)
       */
       static void DynamicProgramming() throws IOException {

              PrintWriter pw = new PrintWriter(new PrintWriter(FOUT));

              int max, pos;

              L[ n ] = 1;

              for(int i = n - 1; i >= 1; i--) {

                   max = 0;

                   for(int j = i + 1; j <= n; ++j) {

                      if( V[j] > V[i] && L[j] > max ) {

                         max = L[j];
                      }
                   }

                   L[i] = 1 + max;
              }


              max = L[1];

              pos = 1;

              for(int i = 2; i <= n; ++i) {

                  if(L[i] > max) {
                    max = L[i];
                    pos = i;
                  }
              }

              pw.println( max );
              pw.print(V[ pos ] + " ");

              for(int i = pos + 1; i <= n; ++i) {

                  if(V[i] > V[pos] && L[i] == max - 1) {

                      pw.print(V[i] + " ");
                      max--;
                  }
              }

              pw.flush();
              pw.close();

       }

       public static void main(String[] args) throws IOException {

        input();
        DynamicProgramming();

       }


}
LIS