mardi 13 mars 2018

How many times update maximum gets called when trying to find the running maximum in a randomized array of numbers?

Suppose we have an array with integers -N to N in an array size of 2N + 1. We first shuffle the elements in the array, then try to find the maximum integer by iterating through the array from the first element to the last element:

int called = 0;
int max = Integer.MIN_VALUE;
for (int i : array) {
    if (i > max) {
        called++;
        max = i;
    }
}

What is the expectation of value called after iterating through the array?




Aucun commentaire:

Enregistrer un commentaire