I have been trying to devise an algorithm for a problem that's been bugging me for a while. For some weird reason I haven't been able to find any mention of this problem in the literature, so far. I find that curious, though, which is why I would like to ask for help here...
In a nutshell, the problem can be stated as follows: Find the largest possible value in an unsorted sequence of numbers that can only be observed incrementally (online). The numbers in the sequence adhere to some unknown distribution, so you can never be completely sure, if you have already found the largest value. You cannot go back to a previous value and once the current value is selected as the "largest possible", the process is stopped.
In pseudo code:
While there are still numbers in the sequence: n = select the next number in the sequence do some analysis with the numbers observed so far if n meets some criterion for being sufficiently large: return n break Repeat
Also, the algorithm should ideally select the first good candidate, instead of running and waiting endlessly.
Does anybody happen to know of an efficient algorithm that solves this problem? Any help would be much appreciated.