You are given an integer array nums. The value of this array is defined as the sum of |nums[i]-nums[i+1]| for all 0 <= i < nums.length-1.
You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.
Find maximum possible value of the final array.
 
Example 1:
Input: nums = [2,3,1,5,4]
Output: 10
Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.

Example 2:
Input: nums = [2,4,9,24,2,1,10]
Output: 68

 
Constraints:

1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5

Difficulty: interview

Starter code:

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)
        base = sum([abs(nums[i] - nums[i+1]) for i in range(n - 1)])
        if (n <= 2):
            return base
        
        #best = base
        #for i in range(n-1):
        #    for j in range(i+1, n):
        #        guess = switch(nums, i, j, base)
        #        if guess > best:
        #            best = guess
        
        inds = sorted(list(range(n)), key=lambda x: nums[x])
        return base + max(options(inds, nums))
        
    
def switch(nums, i, j, base=0):
    i_inc = ((abs(nums[j] - nums[i-1]) - abs(nums[i] - nums[i-1])) if (i > 0) else 0)
    j_inc = ((abs(nums[j+1] - nums[i]) - abs(nums[j+1] - nums[j])) if (j < len(nums) - 1) else 0)
    return base + i_inc + j_inc
    
    

def options(inds, nums):
    a,b = findRange(inds)
    d,c = findRange(inds[::-1])
    yield 0
    yield 2 * (nums[c] - nums[b])

    i = max(a, b)
    j = max(c, d)
    n = len(nums)
    yield switch(nums, i, n-1)
    yield switch(nums, j, n-1)
    
    yield switch(nums, 0, i-1)
    yield switch(nums, 0, j-1)
    
    
    
    

def findRange(inds):
    seen = set()
    for i, idx in enumerate(inds):
        if (idx + 1) in seen or (idx - 1) in seen:
            return (idx + 1, idx) if (idx + 1) in seen else (idx-1, idx)
        seen.add(idx)
        


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n=len(nums)
        s=0
        gain=0
        h=float('-inf')
        l=float('inf')
        for i in range(n-1):
            n1=nums[i]
            n2=nums[i+1]
            s+=abs(n1-n2)
            gain=max(gain, 
                 abs(nums[0] - n2) - abs(n1 - n2),
                 abs(nums[n - 1] - n1) - abs(n1 - n2))
            h=max(h,min(n1,n2))
            l=min(l,max(n1,n2))
        return s+max(gain,2*(h-l))


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        vals = [0]*(len(nums)-1)
        for i, n in enumerate(nums[1:]):
            vals[i] = abs(n-nums[i])
        base = sum(vals)
        bonus = 0

        MPP = max(nums[L]+nums[L+1]-vals[L] for L in range(len(nums)-1))
        MPN = max(nums[L]-nums[L+1]-vals[L] for L in range(len(nums)-1))
        MNP = max(-nums[L]+nums[L+1]-vals[L] for L in range(len(nums)-1))
        MNN = max(-nums[L]-nums[L+1]-vals[L] for L in range(len(nums)-1))

        bonus = max(MPP+MNN, MPN+MNP)

        for R in range(0, len(nums)-1):
            bonus = max(bonus, abs(nums[0]-nums[R+1]) - vals[R])

        for L in range(1, len(nums)-1):
            bonus = max(bonus, abs(nums[L-1]-nums[len(nums)-1]) - vals[L-1])

        return base+bonus

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        numsLen = len(nums)
        oldSum = sum([abs(nums[i] - nums[i+1]) for i in range(numsLen-1)])
        if numsLen < 3:
            return oldSum
        
        delta = 0
        for i in range(1, numsLen-1):
            delta = max(delta, abs(nums[i + 1] - nums[0]) - abs(nums[i+1] - nums[i]), abs(nums[-1] - nums[i-1]) - abs(nums[i]-nums[i-1]))
        
        high = float('-inf')
        low = float('inf')
        
        for x, y in zip(nums, nums[1:]):
            high = max(high, min(x, y))
            low = min(low, max(x, y))
        
        return oldSum + max(delta, (high-low)*2)
        
#         numsLen = len(nums)
        
#         def findDelta(l, r):
#             if l == 0 and r == numsLen-1:
#                 return 0
#             if l == 0:
#                 return abs(nums[r + 1] - nums[l]) - abs(nums[r+1] - nums[r])
#             if r == numsLen-1:
#                 return abs(nums[r] - nums[l-1]) - abs(nums[l]-nums[l-1])
            
#             return abs(nums[r + 1] - nums[l]) - abs(nums[r+1] - nums[r]) + abs(nums[r] - nums[l-1]) - abs(nums[l]-nums[l-1])
        
#         # print(findDelta(1,3))
#         oldSum = sum([abs(nums[i] - nums[i+1]) for i in range(numsLen-1)])
        
#         maxDelta = 0
#         for l in range(0, numsLen-1):
#             for r in range(l, numsLen):
#                 maxDelta = max(maxDelta, findDelta(l, r))
#         return oldSum + maxDelta


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        ans = sum(abs(nums[i+1]-nums[i]) for i in range(len(nums)-1))
        d = 0
        for i in range(1, len(nums)-1):
            d = max(d, abs(nums[0]-nums[i+1]) - abs(nums[i]-nums[i+1]),
                       abs(nums[-1]-nums[i-1]) - abs(nums[i]-nums[i-1]))
        high = -math.inf
        low = math.inf
        for x, y in zip(nums, nums[1:]):
            high = max(high, min(x,y))
            low = min(low, max(x,y))
        
        return ans + max(d, (high-low)*2)

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)
    
        s = 0
        for i in range(len(nums)-1):
            s += abs(nums[i] - nums[i+1])
        
        if n <= 2:
            return s
        
        maxup = inc = 0
        minmax = float('inf')
        maxmin = -float('inf')
        for left in range(1,n):
            dis = abs(nums[left]-nums[left-1])
            minmax = min(minmax, max(nums[left], nums[left-1]))
            maxmin = max(maxmin, min(nums[left], nums[left-1]))
            inc = max(inc, abs(nums[0] - nums[left])- dis)
            inc = max(inc, abs(nums[-1] - nums[left-1])- dis)
            
            
        return s +  max(inc,2*(maxmin-minmax))
                
                


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        ans = 0
        for i in range(1, n - 1):
            ans = max(ans,
                      abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]),
                      abs(nums[-1] - nums[i - 1]) - abs(nums[i] - nums[i - 1]))
        small, large = (-1, float('inf')), (-1, -float('inf'))
        for i in range(n):
            if i >= 1:
                if nums[i] >= nums[i - 1]:
                    if small[1] > nums[i]:
                        small = (i, nums[i])
                if nums[i] <= nums[i - 1]:
                    if large[1] < nums[i]:
                        large = (i, nums[i])
            if i < n - 1:
                if nums[i] >= nums[i + 1]:
                    if small[1] > nums[i]:
                        small = (i, nums[i])
                if nums[i] <= nums[i + 1]:
                    if large[1] < nums[i]:
                        large = (i, nums[i])
        return sum([abs(nums[i] - nums[i + 1]) for i in range(n - 1)]) + max(2 * (large[1] - small[1]), 0, ans)


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        totol, res, min2, max2 = 0, 0, float('inf'), -float('inf')
        for a, b in zip(nums, nums[1:]):
            totol += abs(a - b)
            res = max(res, abs(nums[0] - b) - abs(a - b))
            res = max(res, abs(nums[-1] - a) - abs(a - b))
            min2, max2 = min(min2, max(a, b)), max(max2, min(a, b))
        return totol + max(res, (max2 - min2) * 2)

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        n = len(nums)
        if(n==1):
            return 0
        if(n==2):
            return abs(nums[1]-nums[0])
        
        base = 0
        for i in range(n-1):
            base = base + abs(nums[i+1]-nums[i])
        res = base
        for i in range(1, n-1):
            if(res<base+abs(nums[i+1]-nums[0])-abs(nums[i+1]-nums[i])):
                res = base+abs(nums[i+1]-nums[0])-abs(nums[i+1]-nums[i])
        
        for i in range(1, n-1):
            if(res<base+abs(nums[i-1]-nums[n-1])-abs(nums[i]-nums[i-1])):
                res = base+abs(nums[i-1]-nums[n-1])-abs(nums[i]-nums[i-1])
        
        
        currMax = (nums[0], nums[1])
        currMin = (nums[0], nums[1])
        for i in range(1, n-1):
            curr = (nums[i], nums[i+1])
            if(min(currMax)>max(curr)):
                if(res < base + 2*(min(currMax)-max(curr))):
                    res = base + 2*(min(currMax)-max(curr))
            
            if(max(currMin)<min(curr)):
                if(res < base + 2*(min(curr)-max(currMin))):
                    res = base + 2*(min(curr)-max(currMin))
            if(min(curr)>min(currMax)):
                   currMax = curr
            if(max(curr)<max(currMin)):
                   currMin = curr
        
                   
        return res
            


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        return sum(abs(a-b) for a,b in zip(nums,nums[1:])) + max(max(abs(nums[0]-b)-abs(a-b) for a,b in zip(nums,nums[1:])),max(abs(nums[-1]-a)-abs(a-b) for a,b in zip(nums,nums[1:])),2*(max(min(a,b) for a,b in zip(nums,nums[1:]))-min(max(a,b) for a,b in zip(nums,nums[1:]))))

class Solution:
  def maxValueAfterReverse(self, nums: List[int]) -> int:
    # TC: O(N), SC: O(1), one pass
    # 1. reverse A[0] -- A[i], improve abs(A[0] - A[i+1]) - abs(A[i] - A[i+1])
    # 2. reverse A[i+1] -- A[n-1], improve abs(A[n-1] - A[i]) - abs(A[i] - A[i+1])
    # 3. reverse A[i+1] -- A[j], improve abs(A[i] - A[j]) + abs(A[i+1] - A[j+1]) - abs(A[i] - A[i+1]) - abs(A[j]-A[j+1])
    #   let A[i], A[i+1], A[j], A[j+1] be u, v, x, y and say u = max(u, v, x, y) will always be +u after disclose abs(),
    #   and y = min(u, v, x, y) will always be -y after disclose abs(), so they wil cancel out, and the improve will be
    #   2v - 2x if v >= x or 2x - 2v otherwise, e.g., (max(min(A[i], A[i+1])) - min(max(A[j], A[j+1]))) * 2
    ans, imp1, min2, max2 = 0, 0, float('inf'), -float('inf')
    for x, y in zip(nums[:-1], nums[1:]):
      ans += abs(x - y)
      imp1 = max(imp1, abs(nums[0] - y) - abs(x - y), abs(nums[-1] - x) - abs(x - y))
      min2, max2 = min(min2, max(x, y)), max(max2, min(x, y))
    return ans + max(imp1, (max2 - min2) * 2)

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)-1):
            ans += abs(nums[i+1]-nums[i])
        
        d = 0
        for i in range(1,len(nums)-1):
            d = max(d, abs(nums[0]-nums[i+1]) - abs(nums[i]-nums[i+1]),
                       abs(nums[-1]-nums[i-1]) - abs(nums[i]-nums[i-1]))
        high = -sys.maxsize
        low = sys.maxsize
        for x, y in zip(nums, nums[1:]):
            high = max(high, min(x, y))
            low = min(low, max(x, y))
        return ans + max(d, (high-low)*2)
        


class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        # 三种情况，从头到中间某个地方进行reverse；
        # 从中间到最后进行reverse，中间的某一段进行reverse
        total, res, min2, max2 = 0, 0, float('inf'), float('-inf')
        for a, b in zip(nums[:-1], nums[1:]):
            total += abs(a - b)
            res = max(res, abs(nums[0] - b) - abs(a - b))
            res = max(res, abs(nums[-1] - a) - abs(a - b))
            min2, max2 = min(min2, max(a, b)), max(max2, min(a, b))
        return total + max(res, (max2 - min2) * 2)

class Solution:
    def maxValueAfterReverse(self, nums: List[int]) -> int:
        ans = sum(abs(nums[i + 1] - nums[i]) for i in range(len(nums) - 1))
        d = 0
        for i in range(1, len(nums) - 1):
            d = max(d, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]),
                       abs(nums[-1] - nums[i - 1]) - abs(nums[i] - nums[i - 1]))
        
        
        high = -math.inf
        low = math.inf
        for x, y in zip(nums, nums[1:]):
            high = max(high, min(x, y))
            low = min(low, max(x, y))
        return ans + max(d, (high - low) * 2)

import sys

from collections import defaultdict
from typing import List


class Solution:
  def maxValueAfterReverse(self, nums: List[int]) -> int:
    result = 0

    gain = - sys.maxsize
    hi = -sys.maxsize
    lo = sys.maxsize
    for index in range(len(nums) - 1):
      n1 = nums[index]
      n2 = nums[index + 1]
      result += abs(n1 - n2)
      gain1 = - abs(n1 - n2) + abs(n2 - nums[0])
      gain2 = - abs(n1 - n2) + abs(n1 - nums[-1])
      gain = max(gain, gain1, gain2)
      hi = max(hi, min(n1, n2))
      lo = min(lo, max(n1, n2))

    newgain = 2 * (hi - lo)
    result += max(gain, newgain)
    return result