Make a perfect Split based on absolute difference between max of two arrays 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 &lt; 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?
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 &lt; i and from the "future" > i.