Swift Heap solution, O(n + klogn)
Approach\n\nInstead of sorting the array, we turn it into a heap.\nThen we loop at max k times, and get the minimum number. \nThis number can be either negative
# Approach\n\nInstead of sorting the array, we turn it into a heap.\nThen we loop at max $$k$$ times, and get the minimum number. \nThis number can be either negative/zero, or positive. \n\nIf it\'s negative, we turn it into a positive one and reinsert into the heap. \n\nIf it\'s positive, we don\'t have much to do, so we have two options: flip the same element until we run out of $$k$$, or flip the smallest element to minimise the damage to the final score.\n\nWe can only flip the same element in place if we have an even number of tries left. Otherwise, we flip the smallest element and readd it to the heap.\n\nFinally, we get the sum of heap elements to produce the result.\n\n# Complexity\n- Time complexity:\n$$O(n + k*logn)$$\nCreating the heap and traversing it at the end is $$O(n)$$.\nWe do at worst $$k$$ iterations of inserting/removing from the heap, each of which takes $$O(logn)$$.\n\n- Space complexity:\n$$O(n)$$\nThe heap takes $$O(n)$$ of space.\n\n# Code\n```\nimport Collections\n\nclass Solution {\n    func largestSumAfterKNegations(_ nums: [Int], _ k: Int) -> Int {\n        var heap = Heap(nums)\n\n        for i in 0..<k {\n            let minNum = heap.removeMin()\n            if minNum > 0 {\n                let multiplier = (k - i).isMultiple(of: 2) ? 1 : -1\n                heap.insert(minNum * multiplier)\n                return heap.unordered.reduce(0, +)\n            } else {\n                heap.insert(-minNum)\n            }\n        }\n\n        return heap.unordered.reduce(0, +)\n    }\n}\n```
['Swift', 'Heap (Priority Queue)']