本文主要是介绍Cracking The Coding Interview 9.7，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//原文：
//
// 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)
//
#include <iostream>
#include <algorithm>
using namespace std;struct people
{
public:people(){};people(int _h, int _w){h = _h; w = _w;};int h;int w;
};bool compare(const people &p1, const people &p2)
{if ( p1.h == p2.h){return p1.w < p2.w;}return p1.h < p2.h;
}//求最长子序列，参考http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html#1
int getLIS(people *p, int size)
{int *length = new int[size];for (int i = 0; i<size ; i++){length[i] = 1;}for (int i =0; i <size ; i++){for (int j = i+1; j<size; j ++){if (p[i].w < p[j].w){length[j] = max(length[j], length[i] + 1); }}}int n = length[0];for (int i = 0; i < size; i++){n = (length[i]>n? length[i]:n);}return n;
}int main()
{people p[5] = {people(2,10), people(5,18), people(4,17), people(3,9), people(7,20)};for (int i = 0; i<5; i++){cout<<p[i].h<<" "<<p[i].w<<endl;}cout<<"============="<<endl;sort(p,p+5,compare);for (int i = 0; i<5; i++){cout<<p[i].h<<" "<<p[i].w<<endl;}cout<<getLIS(p,5)<<endl;return 0;
}这篇关于Cracking The Coding Interview 9.7的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
