3236189
When you are iterating along the array and you are at the point of(let () be the current min and [] be the max) and then {} be the item you are looking at)
3(2)3[6]{1}89
At this point you have a 2 as the min and a 6 as the max so your total min-max = 4 and you are looking at the 1 which has the potential to be a better candidate. However that depends on what comes after, if instead of 89 you had 34 then the 2,6 pair would be the best in the bunch. You need to know(or at least I thought) all of the later items to figure out the current item. So I thought well stink there is no clean solution(even thought the website mentioned that there was) and you are at best O(n^2) but as I thought further I realized that you could easily sort the array O(nln(n)) and then step through the original array and know what the future holds so you could evaluate the pair as you are on that item. That would give you O(nln(n) + n) which is of course O(nln(n) so even if you did a dumb way the did way more work than required you could do better then n^2 so I thought about it some more and I think I found the solution. Just a sec while I go write some code to verify that.
Ok here we go, now keep in mind I am not a python guy so I probably did not do things the python way. Sorry recovering c++ programmer here.
import random class pair: "Storing a pair of values and the magnitude of the difference" def __init__(self, minimum, minIndex, maximum, maxIndex): self.minimum = minimum self.maximum = maximum self.minIndex = minIndex self.maxIndex = maxIndex def magnitude(self): return self.maximum - self.minimum def updateMax(self, newMaximum, maxIndex): if newMaximum > self.maximum: self.maximum = newMaximum self.maxIndex = maxIndex def getMin(self): return self.minimum def getMax(self): return self.maximum def printResults(self): return "The answer is %d at the index of %d with a maximum of %d at the index of %d" %(self.minimum, self.minIndex, self.maximum, self.maxIndex) randList = [] for i in range(100): randList.append(random.randint(0,100)) current = pair(randList[0], 0, randList[0], 0); theory = pair(randList[0], 0, randList[0], 0); for i in range(100): current.updateMax(randList[i],i) theory.updateMax(randList[i],i) if theory.magnitude() > current.magnitude(): current = theory if theory.getMin() > randList[i] : theory = pair(randList[i], i, randList[i], i) print current.printResults() print theory.printResults()
