找到整数流中的最大元素

Question

有一个国王。一天他在儿子的日子里决定找到王国最美丽的姑娘嫁给他的儿子。同样，他称这个王国的所有女孩。所有的女孩都排队等候，并在国王面前打电话。国王可以保留女孩或将其送走。一旦一个女孩被派往国外，就不能再被召唤出国。建立一个战略，让国王选择最大可能的美丽女孩。没有必要的最漂亮，但他可以选择的最大限度。

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

Answer 1

参见：Secretary problem

Answer 2

我补充一下Mitchnull说。你不能以决定性的方式解决这个问题。解决这个问题的方法是按部就班的。为了证明这一点，简单地假设最美丽的可以是最后一个。

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

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