1.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 231 Testing the CATCHER
* Link: http://uva.onlinejudge.org/external/2/231.pdf
*
* @author Rolf Schirm
* @version 1.0, 04/01/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.160
*/
public class Main {
public static void main(String... args) throws Exception {
BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));

// Map with the maximum possible intercepts as value
// for a key at the last element of the list
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

String line;

// Maximum possible interceptions
int max = 0;

// Test # count
int count = 1;

while((line = reader.readLine())!= null) {
// New test case or end of input
if(line.equals("-1")) {
// End of input
if(map.isEmpty()) {
break;
}
System.out.println("Test #" + count +":");
System.out.println(" maximum possible interceptions: " + max);
map.clear();
max = 0;
count++;
} else {
// One blank line between two two test cases but not after the last
test case!
if(count > 1 && map.isEmpty()) {
System.out.println();
}

// Current element
int currentNumber = Integer.parseInt(line);

// Maximum possible intercepts with currentNumber as the last element
int maxValue = 0;

// Find the most possible interceptions with currentNumber at the end
for(Integer key: map.keySet()) {
// The last element must be greater or equals the currentNumber
if(currentNumber <= key) {
int value = map.get(key);

// Save the value if its the maximum
if(value > maxValue) {
maxValue = value;
}
}
}

// Increment the maximum value because the currentNumber is added
// as the last element
maxValue++;

// Check if its the new maximum for the possible interceptions
if(maxValue > max) {
max = maxValue;
}

// Store the new value for currentNumber in the map
map.put(currentNumber, maxValue);
}
}
}
}

2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 231 - Testing the Catcher
* Link: http://uva.onlinejudge.org/external/2/231.html
*
* @author Bastian Hoecker
* @author Philipp Hauck Thalheim
* @version 1.0, 06/21/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.132
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
static void find_lis(ArrayList<Integer> a, ArrayList<Integer> b) {
ArrayList<Integer> p = new ArrayList<Integer>(a.size());
for (int i = 0; i < a.size(); i++) {
p.add(new Integer(0));
}
int u, v;

if (a.isEmpty())
return;

b.add(0);

for (int i = 1; i < a.size(); i++) {
// If next element a[i] is greater than last element of current
// longest subsequence a[b.back()], just push it at back of "b" and
// continue
if (a.get(b.get(b.size() - 1)) > a.get(i)) {
p.set(i, new Integer(b.get(b.size() - 1)));
b.add(i);
continue;
}

// Binary search to find the smallest element referenced by b which
// is just bigger than a[i]
// Note : Binary search is performed on b (and not a). Size of b is
// always <=k and hence contributes O(log k) to complexity.
for (u = 0, v = b.size() - 1; u < v;) {
int c = (u + v) / 2;
if (a.get(b.get(c)) > a.get(i))
u = c + 1;
else
v = c;
}

// Update b if new value is smaller then previously referenced value
// TODO
if (a.get(i) > a.get(b.get(u))) {
if (u > 0)
p.set(i, new Integer(b.get(u - 1)));
b.set(u, i);
}
}

for (u = b.size(), v = b.get(b.size() - 1); u-- != 0; v = p.get(v)) {
b.set(u, v);
}
}

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

StringBuffer output = new StringBuffer();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
ArrayList<Integer> lis = new ArrayList<Integer>();
ArrayList<Integer> seq = new ArrayList<Integer>();
int ts = 1;

while (true) {
int h = Integer.parseInt(reader.readLine());

if(h!=-1){
seq.add(h);
}
else{
if(seq.size()==0&&h==-1){
output.deleteCharAt(output.length()-1);
break;
}

find_lis(seq, lis);

// Buffering actual output
output.append("Test #"+ts++ +":\n");
output.append(" maximum possible interceptions: "+lis.size()+"\n");
output.append("\n");
lis.clear();
seq.clear();
}

}
System.out.print(output);
}
}

-----------------------------------------------------------------------------------------------------





1.

package testingTheCatcher;
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 231 Testing the Catcher
* Link: http://uva.onlinejudge.org/external/2/231.html
*
* @author Patrick Bédat
* @version 1.0, 11/03/2010
*
* Method : DP
* Status : Accepted
* Runtime: 0.116
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main
{

public static void main(String... args) throws IOException
{
List<Short> incomingMissileHeights = new ArrayList<Short>();
StringBuffer output = new StringBuffer();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int tc = 1;

while(true)
{
short height = Short.parseShort(reader.readLine());

if (height != -1)
{
incomingMissileHeights.add(height);
}
else
{
if(incomingMissileHeights.size() == 0 && height == -1)
{
output.deleteCharAt(output.length()-1);
break;
}

int[] lengths = new int[incomingMissileHeights.size()];
Arrays.fill(lengths, 1);

int maxLength = 1;

if (height == -1)
{
for (int i = 0; i < incomingMissileHeights.size(); i++)
for (int j = i + 1; j < incomingMissileHeights.size(); j++)
if (incomingMissileHeights.get(i) > incomingMissileHeights.get(j) && lengths[i] + 1 > lengths[j])
{
lengths[j] = lengths[i] + 1;
maxLength = Math.max(lengths[j], maxLength);
}

output.append("Test #"+ tc++ +":\n");
output.append(" maximum possible interceptions: "+maxLength+"\n");
output.append("\n");
incomingMissileHeights.clear();
}
}
}

System.out.print(output);
}
}



2.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 231 Testing the Catcher
* Link: http://uva.onlinejudge.org/external/2/231.pdf
*
* @author Barny Porcio
* @version 1.0, 07/01/2010
*
* Method : -
* Status : Accepted
* Runtime: 0.100
*/



import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class catcher231 {

/**
* @param args
* @throws IOException
* @throws NumberFormatException
*/
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testcase = 1;
boolean firstcase = true;
while(true){
int first = Integer.parseInt(br.readLine());
if (first == -1)
return;
LinkedList<Integer> ll = new LinkedList<Integer>();
ll.add(first);
int temp = Integer.parseInt(br.readLine());
while (temp != -1){
ll.add(temp);
temp = Integer.parseInt(br.readLine());
}

int longest[] = new int[ll.size()];
longest[0] = 1;
int allerlaengste = 1;
for (int i = 1; i < ll.size(); ++i){
int laengstes = -1;
for (int i2 = i-1; i2 >= 0; --i2){
if (ll.get(i2)>ll.get(i) )
if (laengstes == -1 || longest[laengstes] < longest[i2])
laengstes = i2;

}
if (laengstes == -1)
longest[i] = 1;
else
longest[i] = longest[laengstes]+1;
if (longest[i] > allerlaengste )
allerlaengste = longest[i];

}
if (firstcase)
firstcase = false;
else
System.out.println();
System.out.println("Test #"+testcase+":");
System.out.println(" maximum possible interceptions: "+allerlaengste);
++testcase;

}

}

}