Problem statement

https://leetcode.com/problems/maximum-of-absolute-value-expression/

Solution

Use the fact that |A| = max(A, -A), then we can say that |A| + |B| = max(A + B, A - B, -A + B, -A - B). Check all possible ways to open brackets - we have 4 of them.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def maxAbsValExpr(self, A, B):
        f = lambda x, y, z: max(a*x + b*y + i*z for a, b, i in zip(A, B, range(len(A))))
        return max(f(a,b,1) + f(-a,-b,-1) for a, b in [(-1, -1), (-1, 1), (1, -1), (1, 1)])