跳转至

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

题目描述

给定一个整数数组 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 <= 105
  • -104 <= nums[i] <= 104

解法

方法一：逆向思维

思考

每次删两端之一对，得分加上剩下的两端之和，直到剩一或两个。正向模拟删除顺序是指数的。

反过来看：奇数长度最后剩一个元素，偶数长度剩一对相邻元素；已删部分的得分等于总和减去留下的那些。

最大化得分即最小化留下的值。奇数减去全局最小，偶数减去最小的相邻两元之和。

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

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

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

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

1
2
3
4
5
6
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))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
}

评论