整数のストリームで最大の要素を見つける

Question

王がいます.1日に彼は息子のb'dayに彼は彼の息子と結婚する王国で最も美しい女の子を見つけることに決めました。同じように、彼は王国のすべての女の子を呼びます。すべての女の子は列に並び、召使は王の前で贈られます。王は女の子を守るか、それを送ることができます。女の子が送られると、再び呼び出されて王の前に贈られることはありません。王が可能な限り美しい女の子を選ぶように戦略を作ってください。最も美しいが、彼が選ぶことのできる最大のものは必要ありません。

この問題は単純に簡単なステートメントに減らすことができます。どのように最大要素を選択することができます来る整数のストリームを与えられます。瞬時にあなたは単一の整数を持っていて、将来の情報は利用できません。

Answer 1

参照：Secretary problem

Answer 2

私はMitchnullが言ったことに追加します。この問題を決定的に解決することはできません。この問題に対する解決策は、確率的である。それを証明するために、最も美しいものが最後になると仮定してください。

私がこの問題について知っているすべての解決策は、多くのシナリオでは実用的ではない少女の数Nに依存します。

問題はインタビュー中に簡単には解決されません。簡単に見つけられない素晴らしい数学的なトリックがあります。