BinarySearch 0708 Largest Sum After K Negations

Problem statement

https://binarysearch.com/problems/Largest-Sum-After-K-Negations/

Solution

Equal to Leetcode 1005. Maximize Sum Of Array After K Negations.

Complexity

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

Code

class Solution:
    def solve(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 or [0]) - (k - i) % 2 * min(A or [0]) * 2