Suppose I have a long array of values. And I know the index where the maximum value is.
At each step, I pick a value under a certain criterion and modify it according to some rules(it is not important here). After each modification, I have to know the maximum value of the array.
The simplest method is to compare the modified value N
and previously maximum value O
and if N > O
then update the maximum value as N
. However things gets tricky if the index which is modified is where the previously maximum value was stored. In this case, I need to sweep array and and find out what is the maximum value which is O(L)
where L
is the length of array.
I want to avoid this worst case complexity.
What is the best way to achieve it? ( algorithm or data structure? )