3496. 最大化配对删除后的得分 🔒 

English Version

题目描述

给定一个整数数组 nums。当数组中元素超过两个时，你必须重复执行以下操作中的一个：

删除最前面的两个元素。
删除最后面的两个元素。
删除第一和最后一个元素。

对于每次操作，将移除的元素之和加到你的总分上。

返回你可以达到的最高分数。

示例 1：

输入：nums = [2,4,1]

输出：6

解释：

可能的操作有：

删除最前面的两个元素 (2 + 4) = 6。剩余的数组是 [1]。
删除最后面的两个元素 (4 + 1) = 5。剩余的数组是 [2]。
删除第一个和最后一个元素 (2 + 1) = 3。剩余的数组是 [4]。

通过删除最前面的两个元素可以得到最高分，因此最终分数是 6。

示例 2：

输入：nums = [5,-1,4,2]

输出：7

解释：

可能的操作是：

删除第一个和最后一个元素 (5 + 2) = 7。剩余的数组是 [-1, 4]。
删除最前面的两个元素 (5 + -1) = 4。剩余的数组是 [4, 2]。
删除最后面的两个元素 (4 + 2) = 6。剩余的数组是 [5, -1]。

通过删除第一个和最后一个元素可以得到最高分，因此最终分数是 7。

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

解法

方法一：逆向思维

根据题目描述，每次操作会移除掉端点的两个元素。因此，当元素个数为奇数时，最终会剩下 1 个元素；当元素个数为偶数时，最终会剩下数组中的连续两个元素。

为了使得删除后的得分最大化，我们应该使得剩下的元素最小。

因此，如果数组 $\textit{nums}$ 元素个数为奇数，那么答案就是数组 $\textit{nums}$ 所有元素的总和 $s$，减去数组 $\textit{nums}$ 中的最小值 $\textit{mi}$；如果数组 $\textit{nums}$ 元素个数为偶数，那么答案就是数组 $\textit{nums}$ 所有元素的总和 $s$，减去数组连续两个元素之和的最小值。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

Python3

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        s = sum(nums)
        if len(nums) & 1:
            return s - min(nums)
        return s - min(a + b for a, b in pairwise(nums))

Java

class Solution {
    public int maxScore(int[] nums) {
        final int inf = 1 << 30;
        int n = nums.length;
        int s = 0, mi = inf;
        int t = inf;
        for (int i = 0; i < n; ++i) {
            s += nums[i];
            mi = Math.min(mi, nums[i]);
            if (i + 1 < n) {
                t = Math.min(t, nums[i] + nums[i + 1]);
            }
        }
        if (n % 2 == 1) {
            return s - mi;
        }
        return s - t;
    }
}

C++

class Solution {
public:
    int maxScore(vector<int>& nums) {
        const int inf = 1 << 30;
        int n = nums.size();
        int s = 0, mi = inf;
        int t = inf;
        for (int i = 0; i < n; ++i) {
            s += nums[i];
            mi = min(mi, nums[i]);
            if (i + 1 < n) {
                t = min(t, nums[i] + nums[i + 1]);
            }
        }
        if (n % 2 == 1) {
            return s - mi;
        }
        return s - t;
    }
};

Go

func maxScore(nums []int) int {
	const inf = 1 << 30
	n := len(nums)
	s, mi, t := 0, inf, inf
	for i, x := range nums {
		s += x
		mi = min(mi, x)
		if i+1 < n {
			t = min(t, x+nums[i+1])
		}
	}
	if n%2 == 1 {
		return s - mi
	}
	return s - t
}

TypeScript

function maxScore(nums: number[]): number {
    const inf = Infinity;
    const n = nums.length;
    let [s, mi, t] = [0, inf, inf];
    for (let i = 0; i < n; ++i) {
        s += nums[i];
        mi = Math.min(mi, nums[i]);
        if (i + 1 < n) {
            t = Math.min(t, nums[i] + nums[i + 1]);
        }
    }
    return n % 2 ? s - mi : s - t;
}