Skip to content

3496. Maximize Score After Pair Deletions 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
 public:
  int maxScore(vector<int>& nums) {
    const int n = nums.size();
    const int sum = accumulate(nums.begin(), nums.end(), 0);
    if (n % 2 == 1)
      return sum - ranges::min(nums);
    int minAdjacentSum = INT_MAX;
    for (int i = 1; i < n; ++i)
      minAdjacentSum = min(minAdjacentSum, nums[i - 1] + nums[i]);
    return sum - minAdjacentSum;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
  public int maxScore(int[] nums) {
    final int n = nums.length;
    final int sum = Arrays.stream(nums).sum();
    if (n % 2 == 1)
      return sum - Arrays.stream(nums).min().getAsInt();
    int minAdjacentSum = Integer.MAX_VALUE;
    for (int i = 1; i < n; ++i)
      minAdjacentSum = Math.min(minAdjacentSum, nums[i - 1] + nums[i]);
    return sum - minAdjacentSum;
  }
}
1
2
3
4
5
6
class Solution:
  def maxScore(self, nums: list[int]) -> int:
    summ = sum(nums)
    if len(nums) % 2 == 1:
      return summ - min(nums)
    return summ - min(a + b for a, b in itertools.pairwise(nums))