Problem statement

https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/

Solution

First of all we want to flip as many negative numbers as possible, starting from the smaller one. If we have enough, just flip them. If we have less than k, we need to look at reminder (k - i) % 2. If it is even number, do nothing, we just flip one number several times. If it is odd, we need to flip min(A), so we subtract it twice from our sum.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def largestSumAfterKNegations(self, A, k):
        A = sorted(A)
        
        i = 0
        while i < len(A) and i < k and A[i] < 0:
            A[i] = -A[i]
            i += 1
        return sum(A) - (k - i) % 2 * min(A) * 2