amazon - 查找整数流中的最大元素

Question

有一个国王。有一天他在儿子的生日那天，他决定找一个王国里最美丽的女孩嫁给他的儿子。同样，他召唤王国中的所有女孩。所有的女孩都排成一队，一接到电话就出现在国王面前。国王可以留下这个女孩，也可以把它送走。女子一经送出，便不能再召见王。制定一个策略，让国王选择尽可能多的漂亮女孩。不一定是最漂亮的，但他可以选择的最大。

这个问题可以简单地简化为一个更简单的陈述。给定一个整数流，你如何选择最大元素。瞬间你只有一个整数，没有未来的信息可用。

Answer 1

见：秘书问题

Answer 2

我补充一下 Mitchnull 所说的话。您无法确定性地解决此问题。这个问题的解决方案是概率性的。为了证明这一点，只需假设最美丽的可能是最后的。

对于这个问题，我知道的所有解决方案都取决于 N，即女孩的数量，这在许多情况下都是不实际的情况。

这个问题在面试中不是很容易解决的，有一些很好的数学技巧，不是很容易找到的。