BinarySearch 0648 Maximum Adjacent Absolute Value Sum After One Reversal

Problem statement

https://binarysearch.com/problems/Maximum-Adjacent-Absolute-Value-Sum-After-One-Reversal/

Solution

Equal to Leetcode 1330. Reverse Subarray To Maximize Array Value.

Complexity

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

Code

class Solution:
    def solve(self, A):
        maxi, mini = -float("inf"), float("inf")
        
        for a, b in zip(A, A[1:]):
            maxi = max(min(a, b), maxi)
            mini = min(max(a, b), mini)
        change = max(0, (maxi - mini) * 2)
        
        for a, b in zip(A, A[1:]):
            tmp1 = - abs(a - b) + abs(A[0] - b)
            tmp2 = - abs(a - b) + abs(A[-1] - a)
            change = max([tmp1, tmp2, change])
    
        return sum(abs(a - b) for a, b in zip(A, A[1:])) + change