程序员代码面试指南（左程云）读书笔记
第四章
最长递增子序列，（搜狐[编程题]马戏团）
题目：给定数组arr ,返回arr的最长递增子序列。
例如：arr=[2,1,5,3,6,4,8,9,7] 返回【1，3，4，8，9】
先介绍O（N*N）的方法，
1，生成长度为N数组dp,dp[i]表示在以arr[i]这个数结尾的情况下，arr[0..i]中的最大递增子序列长度。
2，对第一个arr[0]来说，令dp[0]=1,接下来从左到右依次算出以每个位置结尾的情况下，最长递增子序列长度。
3，假设计算到位置i,求以arr[i]情况下结尾的最长递增子序列长度，即dp[i].如果最长递增子序列以arr[i]结尾，那么arr[0..i-1]中所有比arr[i]小的数都可以作为倒数第二个数。在那么多个倒数的二个数的选择中，以哪个数结尾的最大递增子序列更大，就选哪个作为倒数第二个数。dp[i]=max(dp[j]+1(0<=j<i,arr[j]<arr[i])).
public static int[] MaxChildArray(int[] a){
if(a.length==0){return a;}
int[] dp=new int[a.length];
for(int i=0;i<a.length;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[i]>a[j]){
dp[i]=Math.max(dp[i], dp[j]+1);
}
}
}
return a;
}
接下来dp数组是怎么得到最长递增子序列的呢？
例如：arr=[2,1,5,3,6,4,8,9,7] ，求出来的dp=[1,1,2,2,3,3,4,5,4]
1,遍历dp数组，找到最大值以及位置。dp[7]=5,说明最长递增子序列长度为5.
2，从arr数组的位置7开始向左遍历，如果对某一位置i,既有arr[i]<arr[7],又有dp[i]=dp[7]-1,那arr[i]就是最长递增子序列的倒数第二个数。以此类推。
public int[] getRest(int[] arr,int dp[]){
int len=0;
int index=0;
//找到dp数组中的最大值
for(int i=0;i<dp.length;i++){
if(dp[i]>len){
len=dp[i];
index=i;
}
}
int[] lis=new int[len];
lis[--len]=arr[index];
for(int i=index;i>=0;i--){
if(arr[i]<arr[index] && dp[i]==dp[index]-1){
lis[--len]=arr[i];
index=i;
}
}
return lis;
}
//主方法：
public int[] lisi(int[] arr){
if(arr==null || arr.length==0){return null;}
int[] dp=MaxChildArray(arr);
return getRest(arr,dp);
}
搜狐员工小王最近利用假期在外地旅游，在某个小镇碰到一个马戏团表演，精彩的表演结束后发现团长正和大伙在帐篷前激烈讨论，小王打听了下了解到， 马戏团正打算出一个新节目“最高罗汉塔”，即马戏团员叠罗汉表演。考虑到安全因素，要求叠罗汉过程中，站在某个人肩上的人应该既比自己矮又比自己瘦，或相等。 团长想要本次节目中的罗汉塔叠的最高，由于人数众多，正在头疼如何安排人员的问题。小王觉得这个问题很简单，于是统计了参与最高罗汉塔表演的所有团员的身高体重，并且很快找到叠最高罗汉塔的人员序列。 现在你手上也拿到了这样一份身高体重表，请找出可以叠出的最高罗汉塔的高度，这份表中马戏团员依次编号为1到N。
输入描述:
首先一个正整数N，表示人员个数。 之后N行，每行三个数，分别对应马戏团员编号，体重和身高。
输出描述:
正整数m，表示罗汉塔的高度。
输入例子:
6
1 65 100
2 75 80
3 80 100
4 60 95
5 82 101
6 81 70
输出例子:
4
解题思路；
和上面的最长递增子序列算法原型相同，只是增加了对体重的排序。
package com.chen.souhu;
import java.util.Scanner;
public class Main {
static class Person {
int num;
int high;
int weight;
int dp;//表示已该人为第一个罗汉的情况下，可以叠几个。
int getNum() {
return num;
}
public void setNum(int num) {
this.num = num;
}
public int getHigh() {
return high;
}
public void setHigh(int high) {
this.high = high;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getDp() {
return dp;
}
public void setDp(int dp) {
this.dp = dp;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
Person map[] = new Person[n];
for (int i = 0; i < n; i++) {
map[i] = new Person();
map[i].setNum(sc.nextInt());
map[i].setWeight(sc.nextInt());
map[i].setHigh(sc.nextInt());
}
sort(map);
int maxH = getRes(map, n);
System.out.println(maxH);
}
}
public static void sort(Person[] map){
// 根据体重排序
for (int i = 0; i < map.length; i++) {
for (int j = i; j > 0; j--) {
if (map[j].getWeight() < map[j - 1].getWeight()) {
Person p=map[j];
map[j]=map[j-1];
map[j-1]=p;
}
// 如果体重相同，身高矮的在后面
else if (map[j].getWeight() == map[j - 1].getWeight()
&& map[j].getHigh() > map[j - 1].getHigh()) {
Person p=map[j];
map[j]=map[j-1];
map[j-1]=p;
} else {
break;
}
}
}
}
//根据体重排序，然后根据身高求dp
public static int getRes(Person[] map, int n) {
int dp = 0;
for (int i = 0; i < n; i++) {
map[i].setDp(1);
for (int j = 0; j < i; j++) {
if (map[i].getHigh() >= map[j].getHigh() && map[i].getDp() < map[j].getDp() + 1) {
map[i].setDp(map[j].getDp() + 1);
}
}
dp = Math.max(dp, map[i].getDp());
}
return dp;
}
}