1.


import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 497 Strategic Defense Initiative
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=6&problem=438&mosmsg=Submission+received+with+ID+8069729

*
* @author Rolf Schirm
* @version 1.0, 03/30/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.444
*/
public class Main {
public static void main(String... args) throws Exception {
final BufferedReader reader = new BufferedReader(new
InputStreamReader(System.in));
final Map<Integer, List<Integer>> map = new TreeMap<Integer,
List<Integer>>();

String line;

// Empty list used for to init the maxList and maxValueList
final List<Integer> emptyList = new ArrayList<Integer>();

// List of the maximum hits
List<Integer> maxList = emptyList;

// Number of test cases - not used
reader.readLine();

// Blank line
reader.readLine();

while((line = reader.readLine())!= null) {
// New test case
if(line.isEmpty()) {
System.out.println("Max hits: " + maxList.size());

for(Integer i: maxList) {
System.out.println(i);
}

// Blank line between two test cases
System.out.println();

// Reset to the init state
maxList = emptyList;
map.clear();
} else {
// Current element
int currentNumber = Integer.parseInt(line);

// Maximum hit list for the currentNumber
List<Integer> maxValueList = emptyList;

// Needless map entries
Set<Integer> removeSet = new HashSet<Integer>();

// Find the most hits with currentNumber at the end
for(Integer key: map.keySet()) {
// The last element must be less or equals the currentNumber
if(key <= currentNumber) {
List<Integer> valueList = map.get(key);

// Save the list with the maximum hits
if(valueList.size() > maxValueList.size()) {
maxValueList = valueList;

// Save needless map entries to remove it afterwards
} else {
removeSet.add(key);
}
} else {
break;
}
}

// Remove needless elements from the map
for(Integer key: removeSet) {
map.remove(key);
}

// List of hits with the currentNumber at the end
List<Integer> numberList;

// Store a clear list at the key currentNumber in the map
if(map.containsKey(currentNumber)) {
numberList = map.get(currentNumber);
numberList.clear();
}
else {
numberList = new ArrayList<Integer>();
map.put(currentNumber, numberList);
}

// Store the new values in the numberList
for(Integer i: maxValueList) {
numberList.add(i);
}

// Add the currentNumber to the end of this list
numberList.add(currentNumber);

// Check if its the new maximum hit list
if(numberList.size() > maxList.size()) {
maxList = numberList;
}
}
}

// Last output
System.out.println("Max hits: " + maxList.size());

for(Integer i: maxList) {
System.out.println(i);
}

// No blank line at the last output!
}
}





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

1.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 497 Strategic Defense Initiative
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=6&problem=438&mosmsg=Submission+received+with+ID+8069729
*
* @author Barny Porcio
* @version 1.0, 07/01/2010
*
* Method : LIS
* Status : Accepted
* Runtime: 0.392
*/

public class StrategicDefenseInitiative497 {


public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


int testcases = Integer.parseInt(br.readLine());
br.readLine();
boolean first = true;
for(int c = 0; c < testcases; ++c){
LinkedList<Integer> ll = new LinkedList<Integer>();
while(true){
String s = br.readLine();
if(s == null || s.isEmpty()) {
break;
}
ll.add(Integer.parseInt(s));
}

int[] lastneighbor = new int[ll.size()];
int biggest = 0;
int[] longest = new int[ll.size()];
longest[0] = 1;
lastneighbor[0] = -1;
for (int i = 1; i < ll.size(); ++i){
int momentanerwert = ll.get(i);
int vergleich= i;
for (int i2 = i-1; i2 >=0; --i2){
if (ll.get(i2) < momentanerwert && longest[i2] > longest[vergleich] ){
vergleich = i2;
}

}

longest[i] = longest[vergleich]+1;
if (longest[i] == 1)
lastneighbor[i] = -1;
else
lastneighbor[i] = vergleich;
//lla[i] = (LinkedList<Integer>) lla[vergleich].clone();
//System.out.println(ll.get(i));
if (longest[i] > longest[biggest])
biggest = i;
}
LinkedList<Integer> lla = new LinkedList<Integer>();
int a = biggest;
while(a != -1){
lla.addFirst(a);
a = lastneighbor[a];
}
if (first)
first = false;
else
System.out.println();
System.out.println("Max hits: "+lla.size());
for (int i : lla){
System.out.println(ll.get(i));
}
}
}

}