What is the core strategy for Maximize Sum Of Array After K Negations?

Use a greedy approach: always flip the smallest (most negative) element and track the array invariant to ensure sum maximization.

How do I handle leftover k when all negatives are flipped?

Continue flipping the element with the smallest absolute value to preserve the sum, considering repeated flips.

Does sorting the array matter for this problem?

Yes, sorting helps identify the smallest or most negative elements quickly for efficient greedy negations.

Can I flip the same index multiple times?

Yes, repeated flips are allowed and may be necessary to maximize the sum if k is larger than the number of negative elements.

What is the time complexity of the optimal solution?

Sorting the array takes O(n log n), and each flip is O(1), giving an overall O(n log n) time complexity.

#1005

Easy

auto_awesome贪心·invariant

LeetCode 题解工作台

K 次取反后最大化的数组和

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后，返回数组可能的最大和。示例 1：输入： nums = [4,2,3], …

数组贪心排序

题目描述

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

以这种方式修改数组后，返回数组 可能的最大和 。

示例 1：

输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

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

lightbulb

解题思路

方法一：贪心 + 计数

我们观察发现，要使得数组的和尽可能大，就应该尽可能地将数组中的最小负数变成正数。

而题目中元素的范围为 $[-100,100]$ ，因此，我们可以先用哈希表 $\textit{cnt}$ 统计数组 $\textit{nums}$ 中每个元素出现的次数。接着从 $-100$ 开始遍历 $x$ ，如果哈希表中存在 $x$ ，那么我们取 $m = \min(cnt[x], k)$ 作为元素 $x$ 取反的个数，然后我们将 $\textit{cnt}[x]$ 减去 $m$ ，将 $\textit{cnt}[-x]$ 加上 $m$ ，并将 $k$ 减去 $m$ 。如果 $k$ 为 $0$ ，说明操作已经结束，直接退出循环即可。

如果 $k$ 仍然为奇数，且 $\textit{cnt}[0]=0$ ，那么我们还需要取 $\textit{cnt}$ 中最小的一个正数 $x$ ，将 $\textit{cnt}[x]$ 减去 $1$ ，将 $\textit{cnt}[-x]$ 加上 $1$ 。

最后，我们遍历哈希表 $\textit{cnt}$ ，将 $x$ 与 $\textit{cnt}[x]$ 相乘的结果累加，即为答案。

时间复杂度 $O(n + M)$ ，空间复杂度 $O(M)$ 。其中 $n$ 和 $M$ 分别为数组 $\textit{nums}$ 的长度和 $\textit{nums}$ 的数据范围大小。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        cnt = Counter(nums)
        for x in range(-100, 0):
            if cnt[x]:
                m = min(cnt[x], k)
                cnt[x] -= m
                cnt[-x] += m
                k -= m
                if k == 0:
                    break
        if k & 1 and cnt[0] == 0:
            for x in range(1, 101):
                if cnt[x]:
                    cnt[x] -= 1
                    cnt[-x] += 1
                    break
        return sum(x * v for x, v in cnt.items())

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution that greedily flips the smallest element each time.
question_mark
Check if candidate negations preserve or violate the sum invariant.
question_mark
Expect discussion on sorting and handling remaining flips after negatives are exhausted.

warning

常见陷阱

外企场景

error
Neglecting to handle remaining k after all negatives are flipped can reduce sum.
error
Flipping larger numbers instead of the smallest magnitude element can lower the final sum.
error
Ignoring the possibility of repeated flips on the same index can miss optimal outcomes.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Maximize sum when k negations are allowed but some elements are locked.
arrow_right_alt
Minimize sum after k negations instead of maximizing, testing greedy inversion.
arrow_right_alt
Allow fractional flips or weighted negations, requiring variant greedy strategies.

help

常见问题

外企场景

继续练习

#1029 两地调度 #976 三角形的最大周长 #969 煎饼排序