Circus 找最大序列 - chkkch - 博客园

[CareerCup][Google Interview] 找最大序列 - chkkch - 博客园
A circus is designing a tower routine consisting of people standing atop one another's
shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people
in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output: The longest tower is length 6 and includes from top to bottom: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)
http://blog.csdn.net/navyifanr/article/details/20837459
http://www.hawstein.com/posts/9.7.html

bool cmp(person p1, person p2){
    if(p1.h == p2.h) return p1.w < p2.w;
    else return p1.h < p2.h;
}
int lis(person p[], int n){
    int k = 1;
    d[0] = p[0].w;
    for(int i=1; i<n; ++i){
        if(p[i].w >= d[k-1]) d[k++] = p[i].w;
        else{
            int j;
            for(j=k-1; j>=0 && d[j]>p[i].w; --j);//用二分可将复杂度降到O(nlogn)
            d[j+1] = p[i].w;
        }
    }
    return k;
}
    sort(p, p+n, cmp);
    cout<<lis(p, n)<<endl;
http://www.careercup.com/question?id=9339758

Arrays.sort(dimension);

private void getMaxPeople(Dimension [] dimension, int n) {
  int[] h = new int[n];
  Arrays.fill(h, 1);
  for(int i=0;i<n;i++) {
   for(int j=i;j<n;j++){
    if(dimension[j].weight < dimension[i].weight && h[j] < (h[i] + 1))  {
     h[j] = h[i] + 1;
    }
   }
  }
  for(int i=0;i<n;i++) {
   System.out.print(h[i] + " ");
  }
  System.out.println();
 }

Longest increasing subsequence 
http://massivealgorithms.blogspot.com/2014/07/longest-increasing-subsequence-rosetta.html
http://massivealgorithms.blogspot.com/2014/08/longest-monotonically-increasing.html
http://www.cnblogs.com/liyukuneed/archive/2013/05/26/3090402.html

Don't think these are right solution.
https://hellosmallworld123.wordpress.com/2014/05/13/longest-height-of-tower/
The problem looks like sorting, we can sort the person by height, if the height are the same, we sort by weight. Then we go through the sorted to find the longest continuous sequence.
https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap11/Q7_2.java

九度1500-出操队形[微策略面试题]
在读高中的时候，每天早上学校都要组织全校的师生进行跑步来锻炼身体，每当出操令吹响时，大家就开始往楼下跑了，然后身高矮的排在队伍的前面，身高较高的就要排在队尾。突然，有一天出操负责人想了一个主意，想要变换一下队形，就是当大家都从楼上跑下来后，所有的学生都随机地占在一排，然后出操负责人从队伍中抽取出一部分学生，使得队伍中剩余的学生的身高从前往后看，是一个先升高后下降的“山峰”形状。据说这样的形状能够给大家带来好运，祝愿大家在学习的道路上勇攀高峰。(注，山峰只有一边也符合条件，如1,1、2,2、1均符合条件)
Read full article from [CareerCup][Google Interview] 找最大序列 - chkkch - 博客园