-1

Given an array, I would like to calculate the maximum absolute difference in values within a given time window.

If the array were a list of stock prices, for example, this question could be thought of as, "What is the greatest increase or decrease in price within a time window of size w?"

Below is a small example to illustrate the problem. 

# Example array and window size. 
w = 4                         # window size
arr = [49, 51, 45, 42, 42, 46, 49, 49, 50, 53, 54]

# Desired output.
max_diff_in_window = -9      # 42 - 51 = -9 is the largest absolute difference within a time window of 4.
index_start = 1              # 51, the first value to appear from our largest absolute difference pair, is located at index 1.
index_finish = 3             # 42, the second value to appear from our largest absolute difference pair, is located at index 3.

In this example, note the greatest absolute difference in values over the entire array is 11 (53-42). However, this would not be the proper solution since it does not respect the specified window size of 4.

I recognize this problem contains some similarities to the Maximum single-sell profit problem, but there are some important differences. First, is the introduction of the time window. Second, I am looking for greatest absolute difference, which would correspond to the greatest profit or loss, not greatest profit.

I have tried the brute-force solution, but am now trying to determine a more efficient approach. Is there a known dynamic programming solution for this problem?

Adam
  • 997
  • 2
  • 12
  • 21
  • SO is not a coding service. Show what youve got so far and what problems you encounter with your solution. Also see [how to ask](http://stackoverflow.com/help/how-to-ask). Requests for code are offtopic here. –  May 06 '17 at 21:18
  • @Paul I removed the mention of code solutions. I've tried the brute force solution and have been working on a dynamic programming solution (e.g., by modifying the single-sell profit maximization dynamic programming solution). I am wondering if this problem is common or well-known with a known solution. If so, any pointers in the right direction would be appreciated. – Adam May 06 '17 at 21:26
  • If the window-size is fixed the best you can do is traverse the array and search for an index `i` such that `abs(arr[i] - arr[i - windowSize])` is the maximum. There is no faster solution than that (which should be your brute-force approach as well). –  May 06 '17 at 21:40
  • @Paul thanks, but I do not consider the window size "fixed" in this sense. Rather, if the window size is `w=4`, for example, I would consider two adjacent numbers in the array to be eligible for the maximum absolute difference. For example, I would say the maximum absolute difference of the array `[10, 2, 5, 6, 7]` is -8 (determined by values 10 and 2). (If you believe the original problem phrasing is unclear, I am open to suggestions on improving it. I tried to use the phrase "within" a time window to convey this meaning). – Adam May 06 '17 at 21:47
  • @Paul the brute force approach, then, would be to iterate over all window sizes `ww` such that `1 <= ww <= w` and store the maximum absolute difference. I was curious if a more efficient approach may exist. – Adam May 06 '17 at 22:03
  • I've misunderstood the question. Im already working on an answer ;). Should totally be doable in `O(n)`. –  May 06 '17 at 22:04
  • http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array – Matt Timmermans May 07 '17 at 01:29

1 Answers1

2

This can be solved using the dynamic-programming approach from this answer with the minor modification of adding a sliding window.

The good news: it's still O(n). The bad news: since minima "expire", we need a queue to store those, which increases the space-complexity to O(w), where w is the window-size.

def gain(arr, w):
    q_min = collections.deque()
    q_max = collections.deque()
    d = 0
    a = 0
    b = 0

    # loop over all windows of the array of length w (i denotes the endindex)
    for i in range(len(arr)):
        # update the queue holding the minimum within the current window
        while q_min and q_min[0] <= i - w:
            q_min.popleft()

        while q_min and arr[i] <= arr[q_min[-1]]:
            q_min.pop()

        q_min.append(i)

        # update the maximum held within the current window
        while q_max and q_max[0] <= i - w:
            q_max.popleft()

        while q_max and arr[i] >= arr[q_max[-1]]:
            q_max.pop()

        q_max.append(i)

        # check if current minimum makes up for the maximum difference so far
        if abs(d) < abs(arr[q_min[0]] - arr[i]):
            a = q_min[0]
            b = i
            d = arr[b] - arr[a]

        #check if current maximum makes up for the maximum difference so far
        if abs(d) < abs(arr[q_max[0]] - arr[i]):
            a = q_max[0]
            b = i
            d = arr[b] - arr[a]

    return d, a, b

The basic idea is to implement the dynamic algorithm mentioned above and expand it by a search for both the minimum and maximum-values within the window ending at i. A more detailed explanation of the algorithm for finding the minima for all windows of an array can be found here (or here), though this one has minor modifications to comply to different requirements, such as sliding-windows with a starting-index lower than 0 and the possibility to drop the last element in the queue, as the next maximum would be the same element anyways.

For reference (and to make the above algorithm easier to understand), heres the algorithm to list all minima of an array for windows ending at i:

def min_sliding(arr, w):
    q = collections.deque()

    for i in range(len(arr)):
        while q and q[0] <= i - w:
            q.popleft()

        while q and arr[i] <= arr[q[-1]]:
            q.pop()

        q.append(i)
        yield q[0]
Community
  • 1
  • 1