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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Mathematics

Greedy algorithms

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
		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)


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:
		(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)


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