Python, heap. Time: O(N + k ln N), Space: O(1)
\nclass Solution:\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        heapq.heapify(A)\n        for _ in range(K):\n            a = 
```\nclass Solution:\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        heapq.heapify(A)\n        for _ in range(K):\n            a = heapq.heappop(A)\n            heapq.heappush(A, -a)        \n        return sum(A)\n```
['Python', 'Python3']