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.

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.

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. The 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.

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.