1
$\begingroup$

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$
  • $\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$ – John L. Jan 11 '19 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.

| cite | improve this answer | |
$\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 '19 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 '19 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$ – John L. Jan 11 '19 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 '19 at 20:18
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – John L. Jan 11 '19 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.

| cite | improve this answer | |
$\endgroup$

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