叠罗汉I

叠罗汉是一个著名的游戏,游戏中一个人要站在另一个人的肩膀上。同时我们应该让下面的人比上面的人更高一点。已知参加游戏的每个人的身高,请编写代码计算通过选择参与游戏的人,我们多能叠多少个人。注意这里的人都是先后到的,意味着参加游戏的人的先后顺序与原序列中的顺序应该一致。

给定一个int数组men,代表依次来的每个人的身高。同时给定总人数n,请返回最多能叠的人数。保证n小于等于500。

测试样例:

[1,6,2,5,3,4],6

返回:4

解题

最长上升子序列

dp[i] 表示 包括i的最长上升子序列长度

import java.util.*;

public class Stack {
public int getHeight(int[] A, int n) {
// write code here
int[] dp = new int[n];
dp[0] = 1;
int height = -1;
for(int i=1;i< n;i++){
int h = 0; // 应该初始化为 0
for(int j = 0;j<i ;j++){
if(A[i] >= A[j]){
h = Math.max(h,dp[j]);
}
dp[i] = h + 1;
height = Math.max(dp[i],height);
}
}
return height;
}
}
上一篇:Java中的流程控制(一)


下一篇:mongo 安装