I am trying to get better at divide an conquer algorithms and am using this one below as an example. Given an array _in and some length l it finds the start point of a sub array _in[_min_start,_min_start l] such that the lowest value in that sub array is the highest it could possible be. I have come up with a none divide and conquer solution and am wondering how I could go about translating this into one which divides the array up into smaller parts (divide-and-conquer).

def main(_in, l):
    _min_start = 0
    min_trough = None

    for i in range(len(_in) 1-l):
        if min_trough is None:
            min_trough = min(_in[i:i l])
        
        if min(_in[i:i l]) > min_trough:
            _min_start = i
            min_trough = min(_in[i:i l])
    
    return _min_start, _in[_min_start:_min_start l]

e.g. For the array [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6] and a sub array of lenght 3 it would return start position 6 (resulting in the array [3,9,8]).

CodePudding user response：

I'm renaming _in and l to clearer-looking names A and k.

Divide and conquer

Split the array in half. Solve left half and right half recursively. The subarrays not yet considered cross the middle, i.e., they're a suffix of the left part plus a prefix of the right part. Compute k-1 suffix-minima of the left half and k-1 prefix-minima of the right half. That allows you to compute the minimum for each middle-crossing subarray of length k in O(1) time each. The best subarray for the whole array is the best of left-best, right-best and crossing-best.

Runtime is O(n), I believe. As Ellis pointed out, in the recursion the subarray can become smaller than k. Such cases take O(1) time to return the equivalent of "there aren't any k-length subarrays in here". So the time is:

T(n) = { 2 * T(n/2)   O(k)    if n >= k
       { O(1)                 otherwise

For any 0 <= k <= n we have k=n^c with 0 <= c <= 1. Then the number of calls is Θ(n^1-c) and each call's own work takes Θ(n^c) time, for a total of Θ(n) time.

Monoqueue

Not divide & conquer, but O(n).

Sliding window, represent the window with a deque of (sorted) indexes of strictly increasing array values in the window. When sliding the window to include a new value A[i]:

1. Remove the first index from the deque if the sliding makes it fall out of the window.
2. Remove indexes whose array values are larger than A[i]. (They can never be the minimum of the window anymore.)
3. Include the new index i.
4. The first index still in the deque is the index of the current window's minimum value. Use that to update overall result.

Python implementation:

from collections import deque

A = [5, 1, -1, 2, 5, -4, 3, 9, 8, -2, 0, 6]
k = 3

I = deque()
for i in range(len(A)):
    if I and I[0] == i - k:
        I.popleft()
    while I and A[I[-1]] >= A[i]:
        I.pop()
    I.append(i)
    curr_min = A[I[0]]
    if i == k-1 or i > k-1 and curr_min > max_min:
        result = i - k   1
        max_min = curr_min

print(result)