class Solution {
public:
int maxValueAfterReverse(vector<int>& nums) {
}
};
1330. 翻转子数组得到最大的数组值
给你一个整数数组 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原站题解
golang 解法, 执行用时: 48 ms, 内存消耗: 7.1 MB, 提交时间: 2023-05-12 10:01:50
func maxValueAfterReverse(nums []int) int {
value, n := 0, len(nums)
for i := 0; i < n - 1; i++ {
value += Abs(nums[i] - nums[i + 1])
}
mx1 := 0
for i := 1; i < n - 1; i++ {
mx1 = Max(mx1, Abs(nums[0] - nums[i + 1]) - Abs(nums[i] - nums[i + 1]))
mx1 = Max(mx1, Abs(nums[n - 1] - nums[i - 1]) - Abs(nums[i] - nums[i - 1]))
}
mx2, mn2 := -100000, 100000
for i := 0; i < n - 1; i++ {
x, y := nums[i], nums[i + 1]
mx2 = Max(mx2, Min(x, y))
mn2 = Min(mn2, Max(x, y))
}
return value + Max(mx1, 2 * (mx2 - mn2))
}
func Abs(a int) int{
if a < 0{
return -a
}
return a
}
func Max(a,b int) int{
if a < b{
return b
}
return a
}
func Min(a,b int) int{
if a > b{
return b
}
return a
}
python3 解法, 执行用时: 392 ms, 内存消耗: 19.7 MB, 提交时间: 2023-05-12 10:01:28
# 枚举所有可能性
class Solution:
def maxValueAfterReverse(self, nums: List[int]) -> int:
value, n = 0, len(nums)
for i in range(n - 1):
value += abs(nums[i] - nums[i + 1])
mx1 = 0
for i in range(1, n - 1):
mx1 = max(mx1, abs(nums[0] - nums[i + 1]) - abs(nums[i] - nums[i + 1]))
mx1 = max(mx1, abs(nums[-1] - nums[i - 1]) - abs(nums[i] - nums[i - 1]))
mx2, mn2 = -inf, inf
for i in range(n - 1):
x, y = nums[i], nums[i + 1]
mx2 = max(mx2, min(x, y))
mn2 = min(mn2, max(x, y))
return value + max(mx1, 2 * (mx2 - mn2))
golang 解法, 执行用时: 52 ms, 内存消耗: 7.1 MB, 提交时间: 2023-05-12 10:00:54
func maxValueAfterReverse(nums []int) int {
base, d, n := 0, 0, len(nums)
mx, mn := math.MinInt, math.MaxInt
for i := 1; i < n; i++ {
a, b := nums[i-1], nums[i]
base += abs(a - b)
mx = max(mx, min(a, b))
mn = min(mn, max(a, b))
d = max(d, max(abs(nums[0]-b)-abs(a-b), // i=0
abs(nums[n-1]-a)-abs(a-b))) // j=n-1
}
return base + max(d, 2*(mx-mn))
}
func abs(x int) int { if x < 0 { return -x }; return x }
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
java 解法, 执行用时: 13 ms, 内存消耗: 48.6 MB, 提交时间: 2023-05-12 10:00:42
class Solution {
public int maxValueAfterReverse(int[] nums) {
int base = 0, d = 0, n = nums.length;
int mx = Integer.MIN_VALUE, mn = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
int a = nums[i - 1], b = nums[i];
int dab = Math.abs(a - b);
base += dab;
mx = Math.max(mx, Math.min(a, b));
mn = Math.min(mn, Math.max(a, b));
d = Math.max(d, Math.max(Math.abs(nums[0] - b) - dab, // i=0
Math.abs(nums[n - 1] - a) - dab)); // j=n-1
}
return base + Math.max(d, 2 * (mx - mn));
}
}
python3 解法, 执行用时: 276 ms, 内存消耗: 19.7 MB, 提交时间: 2023-05-12 10:00:24
class Solution:
def maxValueAfterReverse(self, nums: List[int]) -> int:
base = d = 0
mx, mn = -inf, inf # 最大值，最小值
for a, b in pairwise(nums):
base += abs(a - b)
mx = max(mx, min(a, b)) # 小中取大
mn = min(mn, max(a, b)) # 大中取小
d = max(d, abs(nums[0] - b) - abs(a - b), # i=0
abs(nums[-1] - a) - abs(a - b)) # j=n-1
return base + max(d, 2 * (mx - mn))