算法数学算法

通过分类讨论拆目标函数中的绝对值

字数统计: 903字   |   阅读时长: 4分
, ,

摘要: 力扣1330：分类讨论拆目标函数中的绝对值

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在优化问题中，如果目标函数带有绝对值，处理起来是比较棘手的。有一些比较简单的情况，可以通过分类讨论的方式拆绝对值，比如下面这个：

力扣 1330 就是这种问题，本文我们解决这道题。

题目

给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。

你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。

请你找到可行的最大 数组值 。

提示：

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

示例 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

题解

算法：分类讨论

记初始的所求值为 S0

若翻转的是 i, j，且 0 < i <= j < n - 1，则目标的变化为:

1
2
3
|A[i - 1] - A[i]| + |A[j] - A[j + 1]|
变为
|A[i - 1] - A[j]| + |A[i] - A[j + 1]|

最大化目标为

拆绝对值

首先拆 |A[i - 1] - A[j]| + |A[i] - A[j + 1]|

在公式中，A[i - 1] 与 A[j] 异号，A[i] 与 A[j + 1] 异号

1
2
3
S = |A[i - 1] - A[j]| + |A[i] - A[j + 1]| - (|A[i - 1] - A[i]| + |A[j] - A[j + 1]|) 
拆绝对值
S = d1 * A[i - 1] - d1 * A[j] + d2 * A[i] - d2 * A[j + 1] - (|A[i - 1] - A[i]| + |A[j] - A[j + 1]|)

其中 d1 和 d2 均为 {1, -1}，于是 S 可以分为只与 i 有关的 F(i) 和只与 j 有关的G(j)。

1
2
F(i) = d1 * A[i - 1] + d2 * A[i] - |A[i - 1] - A[i]| 
G(j) = - d1 * A[j] - d2 * A[j + 1] - |A[j] - A[j + 1]|

因为 0 < i <= j < n - 1，枚举 j，实时计算 G(j)，同时维护 F(1..j) 的最大值 mx_F, 更新 S 使 S 最大化 S = max(S, mx_F + G(j))，进而最大化最终答案 cand = S0 + S

边界特判

翻转 0, j, i, n - 1, 0, n - 1 的情况。

1
2
3
0, n-1 : 就是初始的 S0
0, j : S0 - |A[j] - A[j+1]| + |A[0] - A[j+1]|
i, n-1 : S0 - |A[i] - A[i-1]| + |A[n-1] - A[i-1]|

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;
        // ans 为翻转 (0, n-1) 的结果
        for(int i = 0; i < n - 1; ++i)
            ans += abs(nums[i] - nums[i + 1]);
        int S0 = ans;

        // 翻转 (0, j)
        for(int j = 0; j < n - 1; ++j)
            ans = max(ans, S0 - abs(nums[j] - nums[j + 1]) + abs(nums[0] - nums[j + 1]));

        // 翻转 (i, n-1)
        for(int i = 1; i < n; ++i)
            ans = max(ans, S0 - abs(nums[i] - nums[i - 1]) + abs(nums[n - 1] - nums[i - 1]));

        // 翻转 (i, j)
        for(int d1: {-1, 1})
            for(int d2: {-1, 1})
            {
                int max_F = INT_MIN;
                int S = INT_MIN;
                for(int j = 1; j < n - 1; ++j)
                {
                    int gj = -d1 * nums[j] - d2 * nums[j + 1] - abs(nums[j] - nums[j + 1]);
                    max_F = max(max_F, d1 * nums[j - 1] + d2 * nums[j] - abs(nums[j - 1] - nums[j]));
                    S = max(S, gj + max_F);
                    ans = max(ans, S0 + S);
                }
            }

        return ans;
    }
};
Share