Make a perfect Split based on absolute difference between max of two arrays

Question

I was solving this problem in Python3 on the Codechef website. Here I've to split an array such that the absolute difference between the maximum of both the arrays is maximum.

For example, if the input array is [1, 3, -3] then it can be split in two ways:

Way-1:

[1] and [3,-3] --> Absolute difference between max of arrays is 3-1 = 2

Way-2:

[1,3] and [-3] --> Absolute difference between max of arrays is 3 - (-3) = 6

So the max difference is 6, which is the answer.

Below is my code:

def max_difference(a):
    max_diff = 0
    for i in range(len(a) -1):
        local_diff = abs(max(a[:i+1]) - max(a[i+1:]))
        if max_diff < local_diff:
            max_diff = local_diff
    return max_diff


if __name__ == '__main__':
    arr_count = int(input())
    arr = list(map(int, input().rstrip().split()))
    res = max_difference(arr)
    print(res)

Can you please tell me if this code fine? What improvements can be done?

Answer 1

local_diff = abs(max(a[:i+1]) - max(a[i+1:]))

For every i the entire aray is walked through to find left and right maxima. This is complexity O(N²).

One could have two arrays with left_maxima and right_maxima, O(N), so

local_diff = abs(left_maxima[i] - right_maxima[i])

Then the entire complexity is O(N).

The maxima can be filled with a loop over i, either increasing or decreasing, using:

left_maxima[i] = max(left_maxima[i-1], a[i])         // ++i
right_maxima[i] = max(right_maxima[i+1], a[i])       // --i

It is even so, that one array (left or right) is not needed in the final local_diff loop.

What makes this problem so devious is that at index i an evaluation has to happen from past < i and from the "future" > i.

Answer 2

I was asked this question in an interview and I couldn't solve it at first. Later on, I spent some hours on it and finally, I found a proper solution. You should split array from the first index or from the last index to get the maximum difference. I mean max difference is either Max(A[0,...,A.length-2])-A[A.length-1] or A[0]-Max(A[1,...,A.length-1]). For ex, you splitted array from kth index and you have the max value of whole array on the array on left side. In order to minimize the right side array's max value, you should only get the last item cause it will be included for every cases that you split array from k+1 or k+2 (< n). And vice versa is also same. So as result you should calculate these two values and select best one.

Answer 3

You only need to checkout the biggest value an compare it with the last one

I made some tests using against quadratic approach in pastebin.com/rVMqe5TG. What I realised is:

1. You only need to search for the maximum value and then scan to the right.

2. The trick is checking the last value, see these tests:

   assert solution3([9, -4, -5]) == 14 
   assert solution3([9, -4, 4]) == 5 
   assert solution3([9, -4, 0]) == 9 
   assert solution3([9, -4, 4]) == 5 
   assert solution3([9, -4, 5]) == 4 
   

---

def max_difference(A):
    max_value, i_max_value = max(A), A.index(max_value)
    if i_max_value == len(A) - 1:
        return abs(max(A[:-1]) - max_value)

    last_value = A[-1]
    return abs(max_value - last_value)

---

I don´t have enough points to comment on the accepted answer by Joop but right_maxima[i] = max(right_maxima[i+1], a[i]) does not work because the right list is shrinking (therefore different) in each loop iteration.