< Back





1005. Maximize Sum Of Array After K Negations

We're given an array of integers and asked to maximize it's sum after k negations, with a negation
being the operation of changing a number to it's negative value. We solve this by using a min heap to
keep track of the smallest number. We always want to negate the smallest number because it will have
the minimal effect on the sum. We negate the smallest number k times and return the sum of the array.

The solution is as follows:


  from heapq import heapify, heappush, heappop

  class Solution:
      def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
          heapify(nums)

          for _ in range(k):
              heappush(nums, -heappop(nums))

          return sum(nums)


_ Time Complexity:

  O(n * log(n)) - We heapify conduct n heap operations.

_ Space Complexity:

  O(n) - We store n elements in the heap.