难度: Hard
给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。
请你找到可行的最大 数组值 。
示例 1：
输入：nums = [2,3,1,5,4] 输出：10 解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。
示例 2：
输入：nums = [2,4,9,24,2,1,10] 输出：68
提示：
1 <= nums.length <= 3*10^4-10^5 <= nums[i] <= 10^5运行时间: 203 ms
内存: 19.3 MB
class Solution:
def maxValueAfterReverse(self, a: List[int]) -> int:
n = len(a)
sum_val = 0
mx = float("-inf")
mi = float("inf")
tmp = 0
for i in range(n - 1):
l = a[i]
r = a[i + 1]
c = abs(l - r)
sum_val += c
tmp = max(tmp, abs(a[0] - r) - c)
mi = min(max(l, r), mi)
mx = max(min(l, r), mx)
return sum_val + max(tmp, (mx - mi) * 2)
这道题的关键在于分析如何通过翻转子数组来最大化数组值。由于只能翻转一次，我们需要考虑如何选择子数组以及如何翻转以达到最大化效果。一种方法是寻找数组中某个位置的元素，使得翻转到该位置的子数组能最大化数组值。为了实现这一点，我们可以遍历数组，计算每个位置的贡献，并在遍历过程中记录最大贡献。另外，还需要考虑翻转整个子数组对数组值的影响，这可以通过记录数组中的最小元素和最大元素来实现。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxValueAfterReverse(self, a: List[int]) -> int:
n = len(a)
sum_val = 0
mx = float("-inf")
mi = float("inf")
tmp = 0
for i in range(n - 1):
l = a[i]
r = a[i + 1]
c = abs(l - r)
sum_val += c
tmp = max(tmp, abs(a[0] - r) - c)
mi = min(max(l, r), mi)
mx = max(min(l, r), mx)
return sum_val + max(tmp, (mx - mi) * 2)
在这个算法中，`abs(a[0] - r) - c` 的计算方式用于评估将子数组翻转后可能带来的增加贡献。这里的 `r` 是当前考虑的子数组最右端的元素，`c` 是原数组中这个位置的贡献（即 `abs(a[i] - a[i+1])`）。通过翻转，`a[0]` 和 `r` 会成为新的相邻元素，因此 `abs(a[0] - r)` 是翻转后新的贡献。减去 `c` 是因为我们在计算增加的贡献，需要从总贡献中移除当前位置的原贡献。这种计算方式特别地考虑了翻转后数组首部与某一点的交互，尝试通过这种特殊配置找到可能的最大增加效果。
解题思路中确实主要考虑了数组的第一个元素与其他元素的关系。这是因为在翻转子数组时，子数组的一个端点与数组的首端相连可能产生较大的贡献变化。然而，题解中的方法确实没有直接提及与数组最后一个元素的关系，这可能是一个分析的盲点。实际上，考虑与数组最后一个元素相关的翻转也同样重要，因为这可能在某些情况下提供更大的贡献增加，尤其是当数组的最后一个元素与其他元素相差较大时。
在这个解法中，`mx` 和 `mi` 分别代表在遍历过程中找到的子数组中的最小的最大值和最大的最小值。具体来说，`mx` 是所有考虑的子数组中最小值的最大值，而 `mi` 是所有考虑的子数组中最大值的最小值。通过 `(mx - mi) * 2` 的操作考虑的是整个数组中，选择一个点进行翻转后，能够在不考虑具体位置的情况下，最大化两个子数组端点差的可能性。这种方法尝试在全局上找到可能的最大增加，而不是局限于具体的某一位置。这个操作的有效性取决于 `mx` 和 `mi` 的计算精确性，并且在一些情况下，这种方法可能会提供最大的贡献增加效果。