Problem statement

https://leetcode.com/problems/reverse-subarray-to-maximize-array-value/

Solution

In fact, quite difficult mathematical problem. The idea is that we need to minimize $\delta = |A_i - A_j| + |A_{i+1} - A_{j+1}| - |A_i - A_{i+1}| - |A_j - A_{j+1}|$. Let us consider segments $A_i \to A_{i+1}$ and $A_j \to A_{j+1}$. First one can be written as $[\min(A_i, A_{i+1}), \max(A_i, A_{i+1})]$, second one in similar way. Then we can consider 4 different cases about these segments. To undersand it better, we need to draw images on paper.

  1. They intersect, then it can be shown that there is no way to increase value. 2, 3. One inside another, again no way to increase
  2. They do not intersect. Only in this case delta can be positive.

So, for each pairs of i, j we need to consider all segments and choose difference between pairs of non-intersecting segments. It means that we need to evaluate all maximums among left ends of segments and minimum among right ends of segments. It can be done in linear time. Also we need to deal with cases, when i = 0 or j = n - 2, then we have O(n) cases like this as well.

Complexity

Total time complexity is O(n), space is O(1).

Code

class Solution:
    def maxValueAfterReverse(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