11.7 马戏团叠罗汉

思路：定义好Person的数据结构，按照身高和体重排好序。

solutions[i]代表以person[i]结尾的能够叠起的最多人的解。 

solutions[0]初始化，然后求从1~n的情况。

import java.util.ArrayList;
import java.util.Collections;

public class Solution {

public ArrayList<Person> getIncreasingSequence(ArrayList<Person> people) {
        Collections.sort(people);
        ArrayList<ArrayList<Person>> solutions = new ArrayList<ArrayList<Person>>();
        ArrayList<Person> first = new ArrayList<Person>();
        first.add(people.get(0));
        solutions.add(first);

for (int i = 1; i < people.size(); i++) {
            Person cur = people.get(i);
int len = 0;
int longestPre = -1;
for (int j = 0; j < i; j++) {
                ArrayList<Person> pre = solutions.get(j);
if (cur.isBigger(people.get(j))) {
if (solutions.get(j).size() > len) {
                        len = pre.size();
                        longestPre = j;
                    }

                }

            }
            ArrayList<Person> curSolu = new ArrayList<Person>();
if (longestPre != -1)
                curSolu.addAll(solutions.get(longestPre));
            curSolu.add(cur);
            solutions.add(curSolu);

        }

int longestLen = 1;
int longestIdx = -1;
for (int i = 0; i < people.size(); i++) {
if (solutions.get(i).size() > longestLen) {
                longestLen = solutions.get(i).size();
                longestIdx = i;
            }
        }

return solutions.get(longestIdx);

    }

public static void main(String[] args) {
        ArrayList<Person> persons = initialize();
        System.out.println(new Solution().getIncreasingSequence(persons));
    }

public static ArrayList<Person> initialize() {
        ArrayList<Person> items = new ArrayList<Person>();

        Person item = new Person(65, 60);
        items.add(item);

        item = new Person(70, 150);
        items.add(item);

        item = new Person(56, 90);
        items.add(item);

        item = new Person(75, 190);
        items.add(item);

        item = new Person(60, 95);
        items.add(item);

        item = new Person(68, 110);
        items.add(item);

        item = new Person(35, 65);
        items.add(item);

        item = new Person(40, 60);
        items.add(item);

        item = new Person(45, 63);
        items.add(item);

return items;
    }
}

class Person implements Comparable<Person> {
int w;
int h;

public Person(int w, int h) {
this.w = w;
this.h = h;
    }

public int compareTo(Person p) {
if (h != p.h)
return ((Integer) h).compareTo(p.h);
else
return ((Integer) w).compareTo(p.w);
    }

public String toString() {
return "(" + w + "," + h + ")";
    }

public boolean isBigger(Person b) {
if (this.w > b.w && this.h > b.h)
return true;
else
return false;
    }

}