3
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$
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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Suggestion of an alternative approach may be helpful, but please try to review the actual code posted. This sounds like an independent attempt at the same problem, and doesn't explain how and when your method might be better. \$\endgroup\$ – Toby Speight Nov 6 '18 at 9:39
1
\$\begingroup\$

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.

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you expand on this a little? Perhaps explain to the OP and others why this works... \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 6 at 18:17
  • \$\begingroup\$ When adding additional information you should edit your question instead of adding a comment. I have added that information to your post. Learn more about comments including when to comment and when not to in the Help Center page about Comments. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ May 9 at 19:35
  • \$\begingroup\$ Many thanks @SᴀᴍOnᴇᴌᴀ for teaching me the right way of posting! \$\endgroup\$ – kchimba May 10 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.