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();
}
}