1330. Reverse Subarray To Maximize Array Value

题目信息

题号:

1330

难度:

Hard

主题:

数组、区间反转、贪心

原题:

LeetCode 1330

重点:

数组价值为相邻元素差绝对值之和;最多反转一个连续子数组,使价值最大

题目重述

给定整数数组 nums,其价值定义为所有 |nums[i] - nums[i+1]| 的总和。

可以选择至多一个连续子数组并将其中元素顺序反转。请返回操作后能够得到的最大数组价值;长度为一的反转等价于不改变数组。

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

自建示例

反转中间到末尾的区间可以增大边界差:

输入:nums = [2,3,1,5]
输出:9
解释:反转下标 [1,3] 后得到 [2,5,1,3],价值为 3+4+2=9。

所有元素相同时价值始终为零:

输入:nums = [4,4,4]
输出:0
解释:任何反转都不会产生相邻差。