Sum of absolute difference of values and corresponding indices of an array

Question

I am solving questions on arrays from here.

Problem: You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of:

f(i, j) for all 1 ≤ i, j ≤ N.

f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Solution approach:

|A[i] - A[j]| + |i - j| gives us 4 cases:

Case1:|A[i] - A[j]| + |i - j| = -A[i]+ A[j] - i + j = -(A[i]+ i) + ( A[j] + j)
Case2:|A[i] - A[j]| + |i - j| = -A[i]+ A[j] + i - j = -(A[i] - i) + (A[j]-j)
Case3:|A[i] - A[j]| + |i - j| = A[i]- A[j] - i + j  = (A[i] - i) - (A[j] -j) 
Case4:|A[i] - A[j]| + |i - j| = A[i]- A[j] + i - j  = (A[i] + i) - (A[j] + j)

Cases 1 and 4 are equivalent and can be find as the difference between the max and min value of A[i]+i

Cases 2 and 3 are equivalent and can be find as the difference between the max and min value of A[i]-i

How can I perfect this code?

def max_abs_diff(array):
    """ returns sum of absolute difference of values and corresponding indices of an array"""
    max1=[]#array to store maximum values given by A[i] + i
    min1=[]#array to store minimum values given by A[i] + i
    max2=[]#array to store maximum values given by A[i] - i
    min2=[]#array to store minimum values given by A[i] - i

    for i, elem in enumerate(array):

        max1.append(elem + i)  
        min1.append(elem + i)
        max2.append(elem - i)
        min2.append(elem - i)

    return max(max(max1) - min(min1) , max(max2)-min(min2))

Test cases:

print max_abs_diff([2,2,2]) == (2)
print max_abs_diff([2,-2,2])== (5)
print max_abs_diff([-4,-2,-3,-4,-5]) == (6)
print max_abs_diff([-1]) == (0)
print max_abs_diff([-5, 1, -3, 7, -1, 2, 1, -6, 5]) == (18)
print max_abs_diff( [6, -3, -2, 7, -5, 2, 1, -7, 6]) == (20)
print max_abs_diff([-5, -2, -1, -4, -7]) == (8)

Answer 1

First of all, I want to say this is really well presented. It just looks neat, with docstrings and comments and such. If you really want to perfect it, check the Python conventions in PEP 8 and linked documents. For example,

An inline comment is a comment on the same line as a statement. Inline comments should be separated by at least two spaces from the statement. They should start with a # and a single space.

and

The docstring is a phrase ending in a period. It prescribes the function or method's effect as a command ("Do this", "Return that"), not as a description; e.g. don't write "Returns the pathname ...".

---

I also very much appreciate the case analysis that has gone into the code to define those four cases, and so to reduce the naively quadratic function to a linear one. (Refering back to comments, that case analysis would not be at all amiss in a comment just after the docstring explaining the internal logic of the function)

Because, per the code and your case analysis, max1 and min1 always contain the same data, you could make the code shorter and reduce its space requirements by only having one of those. (And likewise for max2 and min2) However, see the next section.

---

In terms of the code itself, I suggest getting rid of those arrays. If they are only filled so that you can reduce them to a single maximum or minimum value, you might as well just track the rolling maximum or minimum as you go. This definitely saves space and probably saves time.

I would name the rolling reductions max_sum and max_difference rather than max1 and max2.

---

In terms of testing examples, do look for pathological cases. One case that always deserves to be checked, although it's not always obvious what the behaviour should be, is the case of an empty list.

---

Finally, it is generally worth using Python 3 in preference to Python 2 for new code, and especially practice code.