数学-绝对值-Reverse Subarray To Maximize Array Value

2020-02-11 12:01:21

问题描述：

问题求解：

本题的难度个人感觉还是蛮大的，主要是不容易想到O(n)的解。

对于 …a, [b, … , c], d, …，如果我们将其中的[b, … , c]进行翻转。

如果两线段有重复，必减小原先的值。

如果两线段无重复，必增加原先的值，且diff为2 * gap。

可通过如下的图进行分类讨论。

最后，再对边界做一个处理即可。

int inf = (int)1e9;
    public int maxValueAfterReverse(int[] nums) {
        int res = 0;
        int n = nums.length;
        int diff = 0;
        for (int i = 0; i < n - 1; i++) res += Math.abs(nums[i + 1] - nums[i]);        // 端点不在两顶点
        int min = inf;
        int max = -inf;
        for (int i = 0; i <= n - 2; i++) {
            min = Math.min(min, Math.max(nums[i], nums[i + 1]));
            max = Math.max(max, Math.min(nums[i], nums[i + 1]));
        }
        diff = Math.max(diff, 2 * (max - min));        // 一端点在左顶点
        for (int i = 1; i <= n - 2; i++) {
            diff = Math.max(diff, Math.abs(nums[i + 1] - nums[0]) - Math.abs(nums[i + 1] - nums[i]));
        }        // 一端点在右顶点
        for (int i = 1; i <= n - 2; i++) {
            diff = Math.max(diff, Math.abs(nums[i - 1] - nums[n - 1]) - Math.abs(nums[i - 1] - nums[i]));
        }        return res + diff;
    }