CS theory problem: evaluating each element in an array only once and choosing the largest value

We covered this problem in a theory class back in college.

The setup is this:

You're presented with an array of N values. You know the length of the array, but not the range of values. You are presented the elements one at a time. Each value can be examined only once, and if the value is not chosen when presented it is discarded. The goal is to choose the maximum value.

There is 开发者_开发技巧an algorithm that gives a better than 1/N chance of choosing the maximum, but I can't for the life of me recall what it is.

It's called the secretary problem.

The Simplest way I know of is to iterate through the array. You create a variable, insert the first array value into it, then as you iterate through each value in the array you compare the stored value to the current value and if the current value is larger than the stored value you put the current value into the stored value, replacing the lower value.

The syntax will change based on what programming language you use but a basic representation would be the following:

Dim MaxValue as integer   
Dim ArrayOfN as Array   
Dim N as integer  
Dim i as integer  

ArrayOfN = [0,10,87,6,59,1200,5] 'In this case there are 7 values in the array  
N = 7 'You would typically want to programically get the size of the array but I can't remember the syntax  
MaxValue = ArrayOfN(0)  
For i = 0 to N - 1 'Assumes iteration of 1  
    If MaxValue < ArrayOfN(i) Then    
        MaxValue = ArrayOfN(i)  
    End IF     
Next

I largely used vb for the coding example but I am aware that some of the syntax is incorrect, especially for the array. However since I don't have access currently to ay coding software that is the best I can do. When coding something you can definitively choose the largest value, there isn't any uncertainty. There are more effient ways of doing this as well. For example if you have the ability to use an array.sort feature then you can get the max value in just 2 lines of code. However since you did not state any programing languages, and after seeing yi_H's answer, I am starting to think that you did not want to know how to do program a solution but simply wanted the name of the problem.

See.. this is a kind'a bit mess using such strategy to retrieve the maximum as you can use any of advanced algorithms like fibonacci search or another anyways, here we are certainly checking the elements one by one.. so to make it happen flag up a variable with the max available till know and iterate it along the length of array linearly.. it may be resolved like this

    Arr[n]={  }
    int max=0
    for x in range 0 to n-1
        if max>Arr[x]
            max=Arr[x]
        [END IF]
    get(max)

so finally we will be getting the maximum but on the cost of high time complexity. try to use divide and conquer kind of algos...