1

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

4

1 回答 1

-2

当 N 和 O 是相同的索引时,存储“先前”的先前最大值 (P) 并将 N 与该值进行比较。P 被 N 替换为当前最大值,因此如果 N 减小到 P 值以下,则 P 应该再次成为最大值。

于 2013-05-30T04:55:12.810 回答