LC 1330. Reverse Subarray To Maximize Array Value

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

这题给我最大的启发就是如何处理绝对值，主要还是从这个 帖子 得到启发的. 我看discuss里面还有另外一种 做法，但是实在是有点看不懂，看上去很高效，但是时间复杂度也是O(n). 或许以后再看看吧。

我直接把帖子摘录过来 

There are only three cases: reverse the prefix subarray, postfix array or the mid subarray.
For the mid case, assuming we are reversing a,b....c,d to a,c...b,d, the difference would be:
|c-a|+|d-b|-|b-a|-|d-c|

So we are trying to maxmize it: max(|c-a|+|d-b|-|b-a|-|d-c|) where (c,d) is current pair, and (a,b) is the pair in front of it. This can be simplified as below removing the abs operators:

max(c-a+d-b-|b-a|-|d-c|)
max(c-a+b-d-|b-a|-|d-c|)
max(a-c+d-b-|b-a|-|d-c|)
max(a-c+b-d-|b-a|-|d-c|)
we separate (a,b) and (c,d) and (c,d) for current pair is constant and can be moved out of the max operator:

max(-a-b-|b-a|)+c+d-|d-c|
max(-a+b-|b-a|)+c-d-|d-c|
max(a-b-|b-a|)-c+d-|d-c|
max(a+b-|b-a|)-c-d-|d-c|

and we can keep the record of the history max and thus reduce the two loops into one loop (just similar to the optimization in best time to buy and sell stocks):
mx0=max(-a-b-|b-a|)
mx1=max(-a+b-|b-a|)
mx2=max(a-b-|b-a|)
mx3=max(a+b-|b-a|)

对绝对值求解极大值，可以简单地把所有可能展开，然后求解最大项。

下面是我丑陋不堪的代码。 

"""
假设ab...cd, 如果调换的话，那么差值则是|a-c| + |b-d| - |a-b| - |c-d|.

如何展开这个差值，可以对绝对值做枚举 max of followings
1. a-c+b-d-|a-b|-|c-d| = (a+b-|a-b|) - (c+d+|c-d|)
2. a-c+d-b-|a-b|-|c-d| = (a-b-|a-b|) - (c-d+|c-d|)
3. c-a+b-d-|a-b|-|c-d| = (-a+b-|a-b|) - (-c+d+|c-d|)
4. c-a+d-b-|a-b|-|c-d| = (-a-b-|a-b|) - (-c-d+|c-d|)

这就转换成为一个动态规划问题.

上面是旋转b,c. 没有考虑到A[0]和A[-1]和里面点的旋转，这个需要单独考虑
"""


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)
        base = 0
        for i in range(n - 1):
            base += abs(nums[i] - nums[i + 1])
        if n <= 3:
            return base

        def left_values(a, b):
            x = abs(a - b)
            return [a + b - x, a - b - x, -a + b - x, -a - b - x]

        def right_values(c, d):
            x = abs(c - d)
            return [c + d + x, c - d + x, -c + d + x, -c - d + x]

        ans = 0
        lv = left_values(nums[0], nums[1])
        for i in range(1, n - 1):
            c, d = nums[i], nums[i + 1]
            rv = right_values(c, d)
            res = [x - y for (x, y) in zip(lv, rv)]
            ans = max(ans, max(res))

            lv2 = left_values(c, d)
            lv = [max(x, y) for (x, y) in zip(lv, lv2)]

        for i in range(1, n - 1):
            ans = max(ans, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]))
        for i in range(1, n - 1):
            ans = max(ans, abs(nums[i - 1] - nums[-1]) - abs(nums[i - 1] - nums[i]))

        return ans + base