#1005

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximize Sum Of Array After K Negations

Maximize the sum of an integer array after exactly k negations using a greedy approach and invariant tracking for optimal results.

array greedy sorting

Problem Statement

Given an integer array nums and an integer k, perform exactly k negations on the array elements. Each negation flips the sign of a selected element, and the same element may be chosen multiple times. Return the largest possible sum of the array after k negations. Apply negations strategically to maximize the sum while preserving the array invariant after each step.

Constraints include 1 <= nums.length <= 10^4, -100 <= nums[i] <= 100, and 1 <= k <= 10^4. Examples: nums = [4,2,3], k = 1 results in 5 after flipping 2 to -2; nums = [3,-1,0,2], k = 3 results in 6 after sequential negations; nums = [2,-3,-1,5,-4], k = 2 results in 13 after flipping -3 and -4.

Examples

Example 1

Input: nums = [4,2,3], k = 1

Output: 5

Choose index 1 and nums becomes [4,-2,3].

Example 2

Input: nums = [3,-1,0,2], k = 3

Output: 6

Choose indices (1, 2, 2) and nums becomes [3,1,0,2].

Example 3

Input: nums = [2,-3,-1,5,-4], k = 2

Output: 13

Choose indices (1, 4) and nums becomes [2,3,-1,5,4].

Constraints

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

Solution Approach

Sort and Prioritize Negatives

Start by sorting the array so the most negative numbers are first. Iteratively negate the smallest number k times. This greedy selection ensures each flip contributes maximally to the sum increase.

Handle Remaining Negations

If k remains after all negatives are flipped, repeatedly flip the smallest absolute value element. Flipping the smallest magnitude preserves sum maximization, maintaining the array invariant after each operation.

Sum Calculation

After completing k negations, sum all elements. This step is straightforward but relies on previous greedy choices. Correct handling of repeated flips avoids pitfalls where extra negations could reduce the sum.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array takes O(n log n) and each flip is O(1) if tracked efficiently, so overall time is O(n log n). Space is O(1) extra beyond the array if in-place sorting is used; otherwise O(n) for a copied array.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Greedy + Counting

We observe that to maximize the sum of the array, we should try to turn the smallest negative numbers into positive numbers.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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())

Continue Practicing

#1029 two city scheduling #976 largest perimeter triangle #969 pancake sorting