Cod sursa(job #1317618)

Utilizator BuseSorinFMI Buse Sorin-Marian BuseSorin Data 15 ianuarie 2015 00:24:37
Problema Subsir crescator maximal Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.2 kb
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Scanner;
public class sursa {
	static int bestIndex=-1;
	static int[] A=new int[100000];
	static int[] best=new int[100000];
	static int[] poz=new int[100000];
	static int n=1,max=-1,p=0;
	
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(new FileReader("scmax.in"));
		n=sc.nextInt();
		for(int i=0;i<n;i++){
			A[i]=sc.nextInt();
		}
		solve();
		print();
		sc.close();
	}
	
	public static void solve(){
		best[n-1]=1;
		poz[n-1]=-1;
		max=1;
		p=n-1;
		for(int j=n-2;j>=0;j--){
			poz[j]=-1;
			best[j]=1;
			for(int i=j+1;i<n;i++){
				if(A[j]<A[i] && best[j]<best[i]+1){
					best[j]=best[i]+1;
					poz[j]=i;
					if(max<best[j]){
						max=best[j];
						p=j;
					}
				}
			}
		}
	}
	
	public static void print() throws IOException{
		BufferedWriter writer=new BufferedWriter(new FileWriter("scmax.out"));
		writer.write(String.valueOf(max+1)+"\n");
		int i=p;
		while(i!=-1){
			writer.write(String.valueOf(A[i])+" ");
			i=poz[i];
		}
		writer.close();
	}

}