叠罗汉是一个著名的游戏，游戏中一个人要站在另一个人的肩膀上。为了使叠成的罗汉更稳固，我们应该让上面的人比下面的人更轻一点。已知参加游戏的每个人的体重，请编写代码计算通过选择参与游戏的人，我们多能叠多少个人。注意这里的人都是先后到的，意味着参加游戏的人的先后顺序与原序列中的顺序应该一致。 给定一个int数组men，代表依次来的每个人的身高。同时给定总人数n，请返回做多能叠的人数。保证n小于等于500。 测试样例： [1,6,2,5,3,4],6 返回：4
//最长递增子序列问题，牛客7.29动态规划串讲第一题，看了视频模仿写出了O(nlogn)的解法
class Stack {
public:
int getHeight(vector
// write code here
int *dp = getDP(men, n);//记录以i为结尾的最长递增子序列
int res = 0;
for(int i = 0; i < n; ++i)
res = max(res, dp[i]);
return res;
}
int* getDP(vector
int *dp = new int[n];
int *help = new int[n];//最长子序列为j+1时候，长度为j序列最小值
help[0] = men[0];
dp[0] = 1;
int end = 0;//记录help数组有有效值的末尾
int l = 0;
int r = 0;
for(int i = 1; i < n; ++i){//二分查找
l = 0;
r = end;
while(l <= r){
int mid = l + (r - l)/2;
if(men[i] > help[mid])
l = mid + 1;
else
r = mid - 1;
}
end = max(end, l);//l为第一个比men[i]大的数的位置
help[l] = men[i];
dp[i] = l + 1;
}
return dp;
}
};
