1005-Maximize Sum Of Array After K Negations-Py All-in-One By Talse
Get it Done, Make it Better, Share the Best -- Talse\nI). Min Heap\n| O(T): O(nlgn) | O(S): O(1) | Rt: 48ms | \npython\n    def largestSumAfterKNegations(self, 
**Get it Done, Make it Better, Share the Best -- Talse**\n**I). Min Heap**\n| O(T): O(nlgn) | O(S): O(1) | Rt: 48ms | \n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        heapq.heapify(A)\n        for _ in range(K): heapq.heappush(A, -heapq.heappop(A))\n        return sum(A)\n```\nComment: always negate the minimum. \nAlternative: slightly improved. | Rt: 40ms |\n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        heapq.heapify(A)\n        for _ in range(K % (2 * len(A))): heapq.heappush(A, -heapq.heappop(A))\n        return sum(A)\n```\nComment: if you do 2 * len(A) negating, you can always get the original input list. \nTriple: further improved.  | Rt: 48ms |\n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        heapq.heapify(A)\n        K %= 2*len(A)\n        for i in range(K):\n            if A[0] >= 0: return sum(A) - ((K - i) & 1) * 2 * A[0] \n            heapq.heappush(A, -heapq.heappop(A))\n        return sum(A)\n```\nComment: Once all elements are positive, stop the game and check the remaining times need to modify. If the remaining is even, it is the sum of current list (you negate the minimun even times, it remains the same). Otherwise, you need to deduct the minimum twice because you already added it to the sum once (and it is negative after odd times negating). This should boost the runtime however it didn\'t ....\n\nQuestion: could we reduce K by % 2(len(A))? I think not, but the solution get passed. **I clarify the "Reduce K" trick in the above solutions (and below) may not be applicable in case some troubles .** \n\n\n**II). Remove and Append**\n| O(T): O(kn) | O(S): O(1) | Rt: 136ms | \n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        for _ in range(K): \n            curmin = min(A)\n            A.remove(curmin)\n            A.append(-curmin)\n        return sum(A)\n```\nAlternative: slightly improved.  | Rt: 124ms | O(T): n^2 |\n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        for _ in range(K % (2*len(A))): \n            curmin = min(A)\n            A.remove(curmin)\n            A.append(-curmin)\n        return sum(A)\n```\n\n\n**III). Greedy**\n| O(T): O(nlgn) | O(S): O(1) | Rt: 56ms | \n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        A.sort(); K %= 2 * len(A); i = 0\n        while A[i] < 0 and i < K: A[i], i = -A[i], i + 1\n        return sum(A) - ((K-i) % 2) * 2 * min(A)\n```\n\n\n**IV). Counting Sort**\n| O(T): O(n) | O(S): O(n) | Rt: 56ms | \n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        ct = collections.Counter(A)\n        for i in range(-100, 0):\n            if K == 0: break\n            if i in ct: \n                amt = min(K, ct[i])\n                ct[i] -= amt\n                ct[-i] += amt\n                K -= amt\n        a = list(ct.elements())\n        return sum(a) - (K&1) * 2 * min(a) \n```\nReferrence: https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252254/C++Python-Sort/246430\nComment: take advantage of the -100 <= A[i] <= 100.\n\n\n**V). Bucket Collect then Counting Sort**\n| O(T): O(n) | O(S): O(1) | Rt: 48ms | \n```python\n    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:\n        m = [0] * 201\n        for i in A: m[i+100] += 1\n        for i in range(0, 100):\n            if K == 0: break\n            if m[i]: \n                amt = min(K, m[i])\n                m[i] -= amt\n                # -(i - 100) + 100 = 200 -i\n                m[200 - i] += amt\n                K -= amt\n        suma = sum((i-100) * v for i, v in enumerate(m) if v)\n        # mina = next(i - 100 for i, v in enumerate(m) if v)\n        return suma - (K&1) * 2 * min(map(abs, A)) \n```\nReferrence: idea from https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/discuss/252849/C%2B%2BJava-O(n)-or-O(1)\nQuestion: min([5,6,9,-3,3], key=abs) == -3 and min([5,6,9,-4,3], key=abs) == 3. Who tell me Why?\n
[]