Circus.java

//http://coolcodebro.blogspot.com/2012/12/lognest-increasing-sequence-with-pairs.html

//NOTE: Use some kind of dynamic programming if data is too big

public class Circus {
	public static void main(String[] args) {
		new Circus().run();
	}
	
	void run() {
		List<Pair> pairs = new ArrayList<Pair>();
		
		pairs.add(new Pair(65, 100));
		pairs.add(new Pair(70, 150));
		pairs.add(new Pair(56, 90));
		pairs.add(new Pair(75, 190));
		pairs.add(new Pair(60, 95));
		pairs.add(new Pair(68, 110));
		
		List<Pair> sol = getLongestSequence(pairs);
		printPairs(sol);
	}
	
	List<Pair> getLongestSequence(List<Pair> pairs) {
		Collections.sort(pairs);	//Gotta sort first
		
		List<List<Pair>> longest = new ArrayList<List<Pair>>();

		for(int i=0; i<pairs.size(); i++) {
			Pair pair = pairs.get(i);
			List<Pair> newPairs = new ArrayList<Pair>();
			newPairs.add(pair);
			
			for(int j=0; j<i; j++) {
				List<Pair> currentPairs = longest.get(j);
				Pair currentPair = currentPairs.get(currentPairs.size()-1);

				if(currentPairs.size() < newPairs.size()) continue;
				
				if(pair.compareTo(currentPair) > 0) {
					newPairs.clear();
					newPairs.addAll(currentPairs);
					newPairs.add(pair);
				}
			}

			longest.add(newPairs);
		}
		
		return getMaxSequence(longest);
	}
	
	List<Pair> getMaxSequence(List<List<Pair>> pairs) {
		int ind = 0;
		for(int i=1; i<pairs.size(); i++) {
			if(pairs.get(i).size() > pairs.get(ind).size())
				ind = i;
		}
		
		return pairs.get(ind);
	}
	
	void printPairs(List<Pair> pairs) {
		System.out.println("Length: " + pairs.size());
		
		for(int i=0; i<pairs.size(); i++)
			System.out.printf("(%d, %d) ", pairs.get(i).x, pairs.get(i).y);
		System.out.println();
	}
}

class Pair implements Comparable<Object> {
	int x, y;
	public Pair(int _x, int _y) { x = _x; y = _y; }
	
	@Override
	public int compareTo(Object o) {
		Pair ob = (Pair) o;
		if(x == ob.x && y == ob.y) return 0;
		if(x > ob.x && y > ob.y) return 1;
		return -1;
	}
}