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? )