1
$\begingroup$

This question already has an answer here:

Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an interval of 4 because 8 - 4 = 4. But the largest positive interval is between index 2 and index 10, because 11 - 1 = 10.

I can see that there's a way to do this in linear time, but I can't figure out what it is. The n^2 brute force solution is straightforward, but I want to understand the better way.


To be clear, the largest positive interval in [20, 1, 4] would be 3, not 19, because 20 -> 1 is an interval of -19.


The solution I would put forward is to translate the array in linear time to an array of differences, e.g. [20, 1, 7, 4, 2] becomes [0, -19, 6, -3, -2], and then use Kadane's algorithm for finding the maximum contiguous subsequence. The largest subsequence would be 6 on its own, implying indices 1 and 2 provided the answer.

$\endgroup$

marked as duplicate by xskxzr, David Richerby, Yuval Filmus algorithms Jan 13 at 11:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ "I can see that there's a way to do this in linear time, but I can't figure out what it is. " Try seeing it slowly. Very slowly. $\endgroup$ – Apass.Jack Jan 11 at 19:30
3
$\begingroup$

Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned.

Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result.

$\endgroup$
  • 1
    $\begingroup$ "smallest number so far" -> but then what about the array [100, 300, 1, 10]? The smallest number would be 1, but the largest interval is between 100 and 300. $\endgroup$ – temporary_user_name Jan 11 at 19:52
  • $\begingroup$ Ah, true. (Downvote was not from me.) But "keep track of the largest interval so far" is exactly the problem itself, isn't it? $\endgroup$ – temporary_user_name Jan 11 at 19:58
  • $\begingroup$ Use the smallest number so far to compute the largest interval whose right endpoint is the current number. Update the largest interval overall if that interval turns out larger. My hint might be somewhat illusive. Let me update the hint. $\endgroup$ – Apass.Jack Jan 11 at 20:07
  • $\begingroup$ Well, it seems to be in reference to the brute force n^2 way of doing this. I am still pondering any linear method you could be referring to with that hint. $\endgroup$ – temporary_user_name Jan 11 at 20:18
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Apass.Jack Jan 11 at 20:18
0
$\begingroup$

I know of two solutions:

The first is put forward by @Apass.Jack, and is the simpler and better one:

def maximumInterval(array):
  min_value = array[0]
  max_interval = -1
  for i in range(1, len(array)):
    if array[i] - min_value > max_interval :
        max_interval = array[i] - min_value
    if array[i] < min_value :
        min_value = array[i]
  return max_interval 


result = maximumInterval([4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9])
print(result) 

result  = maximumInterval([20,1,4])
print(result)

The other solution is as described in the question above. Convert the array to an array of differences and find the maximum contiguous subarray using Kadane's algorithm.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.