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

Sungmin
  • 2,499
  • 3
  • 26
  • 32
  • Two words : heap sort. – Jason May 30 '13 at 04:55
  • one link: http://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-efficient-than-on – 0x90 May 30 '13 at 05:02
  • Two links: http://en.wikipedia.org/wiki/Min-max_heap http://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python – 0x90 May 30 '13 at 05:03
  • There's also a question of where the index to be modified comes from. These indices cannot be stored, as each modification potentially invalidates them. Perhaps you want a simple sorted linked list. – n. m. could be an AI May 30 '13 at 05:17
  • @n.m. Only insertions and deletions will invalidate the indices. I can't be sure, but it doesn't look like those are required operations (`"... pick a value ... modify it ..."`). – Bernhard Barker May 30 '13 at 09:38
  • I'm sorry, I think I've misunderstood the description. No you cannot use a linked list. I think the simplest way is indeed to use a heap. – n. m. could be an AI May 30 '13 at 10:13

1 Answers1

-2

Store the "previous" previous maximum (P) and compare N against that value when N and O are the same index. P was replaced by N as the current maximum value, so if N is reduced below the value of P then P should once again be the maximum value.

huene
  • 1
  • 2
  • you don't handle cases of deletion only insertion. – 0x90 May 30 '13 at 05:01
  • @Emil - you're right. N could be modified such that it would not be the second highest value behind "P", resulting in needing to search for the new "P"... didn't think of that. – huene May 30 '13 at 05:16
  • @0x90, ignoring the shortcoming that Emil pointed out for a second, 1) the question stated that an index was modified, not inserted or deleted, and 2) if N was deleted where N === 0, wouldn't "P" still be the maximum value of the array? (also, in the case of insertion, N and O won't be the same index, and this problem goes away...) – huene May 30 '13 at 05:22
  • @huene wasn't read it carefully I was on train, I am leaving all the comments since they point to related subjects. – 0x90 May 30 '13 at 07:01