問題： 有n個數(shù)字，要求你在線的選擇其中一個最大的，在選擇第i個之前，你知道前i-1次的數(shù)字是什么，但是無法知道你將要選擇的數(shù)字和以后待選的數(shù)字的大小。

一個很自然的策略是選定一個K，先看一下前k個的大小，不做任何選擇，然后繼續(xù)看，知道遇到一個比這之前的k個人還好?？梢宰C明k= n/e 的時候，能夠獲得最好的選擇，能夠選擇到最大的那個。證明其實是比較簡單的。假設(shè)在我們的某次選擇中，選擇第i個是最優(yōu)選擇，那么很顯然第i個必須是這n個數(shù)中最大的，那么此時的概率是1/n,第二個要求是前k個數(shù)中存在這i個數(shù)中次大的數(shù)，否則是不會選擇第i個的。此時的概率是k/i-1，所以把第k個到第n個累加起來就OK了，然后取得次數(shù)的最大數(shù),可以計算獲得k=n/e。

很顯然這個問題是一個在線算法的問題，無法預(yù)知之后的情況，邊輸入邊進行處理。而離線算法是要求當(dāng)輸入完成之后，然后進行輸出。 在線算法的目的就是能夠達到離線算法的一樣好的效果。

題目來源：

http://zhiqiang.org/blog/science/tcs-classroom-notes-the-best-dating-strategy.html
http://www.cnblogs.com/fll/archive/2008/06/01/1211569.html