1.

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
 * Problem: 111 History Grading
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&page=show_problem&problem=47
 *
 * @author Patrick Bédat
 * @author Christoph Göttschkes
 * @version 1.0, 11/03/2010
 *
 * Method : DP
 * Status : Accepted
 * Runtime: 0.272
 */
package historyGrading;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main
{
	public static void main(String... args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		int nQuestions = Integer.parseInt(reader.readLine().trim());

		int[] eventRanks = new int[nQuestions+1];
		StringTokenizer st = new StringTokenizer(reader.readLine());

		//every number in the first line is the rank of the i'th event
		for (int event = 1; event <= nQuestions; event++)
		{
			int rank = Integer.parseInt(st.nextToken());
			eventRanks[rank] = event;
		}

		//now the ranked events are translated to their array indizes for "<" comparison
		int[] translatedEventRanks = new int[nQuestions+1];

		for(int i = 1; i <= nQuestions; i++)
		{
			translatedEventRanks[eventRanks[i]] = i;
		}

		do
		{
			int[] studentAnswers = new int[nQuestions+1];

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

			for (int event = 1; event <= nQuestions; event++)
			{
				int answerRank = Integer.parseInt(st.nextToken());
				studentAnswers[answerRank] = event;
			}
			
			int[] length = new int[nQuestions+1];
			Arrays.fill(length, 1);

			int maxLength = 1;

			for (int i = 1; i <= nQuestions; i++)
				for (int j = i + 1; j <= nQuestions; j++)
				{
					int e1 = studentAnswers[j];
					int e2 = studentAnswers[i];

					if (translatedEventRanks[e1] > translatedEventRanks[e2] && length[i] + 1 > length[j])
					{
						length[j] = length[i] + 1;
						maxLength = Math.max(length[j], maxLength);
					}
				}
			
			System.out.println(maxLength);
		}
		while (reader.ready());
	}
}



2. 

/**
 * link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=47&mosmsg=Submission+received+with+ID+8040599
 * ACM 111 History Grading
 * Status: Accepted
 * Time: 0.688
 * @author Christoph Miesel
 */

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

public class History 
{
	static boolean end = false;
	static final int DUMMY = 0;
	static boolean first;
	static int size;
	
	static Integer[] height;
	static Integer[] length; 
	static Integer[] predecessor;
	static ArrayList<Integer[]> rankings = new ArrayList<Integer[]>();
	static Integer[] solution;
	
	static void swap(Integer[] array, int pos1, int pos2)
	{
		int tmp = array[pos1];
		array[pos1] = array[pos2];
		array[pos2] = tmp;
	}
	
	static void initialize()
	{
		length = new Integer[size+1];
		length[0] = DUMMY;		
		for(int l = 1; l < length.length; l++)
			length[l] = 1;
		
		predecessor = new Integer[size+1];
		predecessor[0] = DUMMY;		
		for(int l = 1; l < predecessor.length; l++)
			predecessor[l] = 0;
	}
	
	static void sort()
	{
		int min;
		int index;
		for(int i = 1; i < solution.length-1; i++)
		{
			min = solution[i];
			index = i;
			for(int j = i+1; j < solution.length; j++)
			{
				if(solution[j] < min)
				{
					min = solution[j];
					index = j;
				}				
			}
			swap(solution, i, index);
			for(Integer[] s: rankings)
				swap(s, i, index);
		}
	}
	
	static void increase(Integer[] height)
	{
		for(int i = 1; i < height.length-1; ++i)
		{
			for(int j = i+1; j < height.length; ++j)
				if(height[j] > height[i])
					if(length[i]+1>length[j])
					{
						length[j] = length[i]+1;
						predecessor[j] = i;
					}
		
		}
	}
	
	public static void main(String[] args) throws IOException
	{		
		Scanner sc = new Scanner(System.in);
		size = sc.nextInt();
		
		
		height = new Integer[size+1];
		length = new Integer[size+1];
		predecessor = new Integer[size+1];
		solution = new Integer[size+1];
						
		solution[0] = DUMMY;
		for(int l = 1; l < solution.length; l++)
			solution[l] = sc.nextInt();
										
		while(sc.hasNextInt())
		{
			Integer[] tmp = new Integer[size+1];
			tmp[0] = DUMMY;
			for(int l = 1; l < tmp.length; l++)
				tmp[l] = sc.nextInt();
			rankings.add(tmp);			
		}					
					
		sort();
					
					//System.out.println(Arrays.toString(solution));
					//for(Integer[] s: rankings)
						//System.out.println(Arrays.toString(s));
		
		for(Integer[] s: rankings)
		{
			initialize();
			increase(s);
			int max = 0;
			for(Integer d: length)
				if(d > max)
					max = d;
			System.out.println(max);
		}
			
			//find maximum
			
			rankings.clear();		
	}
}