Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total.  (We may choose the same index i multiple times.)
Return the largest possible sum of the array after modifying it in this way.
 
Example 1:
Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].


Example 2:
Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].


Example 3:
Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].



 
Note:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

Difficulty: introductory

Starter code:

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        

Solutions:
class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        
        i = 0
        while A[i] < 0 and K > 0:
            A[i] *= -1
            i += 1
            K -= 1
            
        if K % 2 == 1 and 0 not in A:
            return sum(A) - 2*min(A)
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        i=0
        while(i<len(A) and A[i]<0 and i<K):
            A[i]=-A[i]
            i+=1
        
        return sum(A)-(K - i) % 2 * min(A) * 2

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        S=0
        negs=[]
        posmin=100
        negmax=-100
        for i in range(len(A)):
            S+=A[i]
            if A[i]<0:
                negs.append(A[i])
                negmax=max(negmax,A[i])
            else:
                posmin=min(posmin,A[i])
        if K is 0:
            return(S)
        negs.sort()
        if K <= len(negs):
            return(S-2*sum(negs[:K]))
        elif (K - len(negs))%2 is 0:
            return(S-2*sum(negs[:K]))
        elif posmin<-negmax:
            return(S-2*sum(negs[:K])-2*posmin)
        else:
            return(S-2*sum(negs[:K])+2*negmax)

class Solution(object):
    def largestSumAfterKNegations(self, A, K):
        lst = sorted(A)
        count = K
        i = 0
        while count>0:
            if lst[i] <= lst[i + 1]:
                lst[i] = lst[i] * -1
                count -= 1
            else:
                i += 1
        return sum(lst)


import heapq
class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        heapq.heapify(A)
        for _ in range(K):
            heapq.heapreplace(A, -A[0])
        return sum(A)
        


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        p = 0
        while A[p] < 0:
            A[p] = - A[p]
            p += 1
            K -= 1
            if K == 0:
                 return sum(A)
        if K % 2 == 0:
            return sum(A)
        else:
            return sum(A) - 2 * min(A[p], A[p-1])

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        heapq.heapify(A)
        #heapify is in place algo so take linear time
        for x in range(K):
            #if x %2 :
                #heappreplace(A, -A[0])
            #heappush(A, -heapq.heappop(A))
            heapreplace(A, -A[0])
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], k: int) -> int:
        d = collections.defaultdict(int)
        for x in A:
            d[x] += 1
        
        res = 0
        for i in range(-100, 0):
            if i in d and k > 0:
                x = min(k, d[i])
                k -= x
                d[i] -= x
                d[-i] += x
            
        res = 0
        if k % 2 == 1:
            j = 0
            while j not in d or d[j] <= 0:
                j += 1
            print(j)
            d[j] -= 1
            d[-j] += 1
        for i in range(-100, 101):
            res += d[i] * i
        return res
        
            
                
                    
            

                


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        res = 0
        A.sort()
        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 * 2 * min(A[i-1:i] + A[i:i+1])
            
        


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for i in range(K):
          A.sort()
          A[0] = -A[0]
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        result = 0
        count = 0
        A.sort()
       
        if A[0] > 0:
            if K%2 == 1:
                A[0] = -A[0]
            for i in A:
                result += i
            return(result)
        elif A[0] == 0:
            for i in A:
                result += i
            return(result)
        else:
            for j in range (len(A)):
                if A[j] >= 0:
                    break
                else:
                    count += 1
            ra = K%count
            if K < count:
                for m in range(K):
                    A[m] = -A[m]
            else:
                for m in range(count):
                    A[m] = -A[m]
                K -= count
                A.sort()
                if K%2 == 1:
                    A[0] = -A[0]
            for i in A:
                result += i
            
            return(result)

class Solution:
    import heapq
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        heapq.heapify(A)
        for i in range(K):
            m = heapq.heappop(A)
            heapq.heappush(A, -m)
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        newA = sorted(A)
        print(newA)
        count = 0
        for i in range(K):
            newA[0] = -newA[0]
            newA = sorted(newA)
        print(newA)
        return sum(newA)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        B = sorted(A)
        for i in range(K):
            B[0] = -B[0]
            B = sorted(B)
        return sum(B)

class Solution:
    def largestSumAfterKNegations(self, arr: List[int], k: int) -> int:
        ra = k
        arr.sort()
        for _ in range(ra):
            for j in range(len(arr)):
                if arr[j] < 0:
                    arr[j] = abs(arr[j])
                    k -= 1
                    arr.sort()
                    break
                elif arr[j] == 0:
                    return sum(arr)
                else:
                    if k % 2 == 0:
                        return sum(arr)
                    else:
                        arr.sort()
                        arr[0] = -arr[0]
                        return sum(arr)

        return sum(arr)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        while K > 0:
            t = A.index(min(A))
            if A[t] < 0:
                A[t] = abs(A[t])
                K -= 1
                continue
            if A[t] == 0:
                K = 0
                continue
            if A[t] > 0:
                if K % 2 == 0:
                    K = 0
                    continue
                else:
                    A[t] = -A[t]
                    K = 0
                    continue
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for x in range(K):
            minNum=A.index(min(A))
            A[minNum]=A[minNum]*(-1)
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for i in range(K):
            variable = min(A)
            A.remove(variable)
            A.append(variable*-1)
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        for i in range(K):
            
            val = min(A)
        
            A.remove(val)
            A.append(-1 * val)
                                
        return sum(A)
                
               


# 5:47 -> 5:50 slowwww
# Seems greedy: pick smallest number and flip it
class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        while K:
            m = min(A)
            m_i = A.index(m)
            A[m_i] = -m
            K -= 1
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:

        for i in range(K):
            min_ = min(A)
            idx = A.index(min_)
            A[idx] = -A[idx]
            max_ = sum(A)
        return max_
            


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        a1 =A
        sum1 =0
        while K > 0 :
            mina = min(a1)
            a1.remove(mina)
            a1.append(mina * (-1))
            K -=1
            
    
        
        return sum(a1)
        


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        for i in range(K):
            A[0] = -1 * A[0]
            if A[0] > A[1]:
                A.append(A.pop(0))
        return sum(A)        

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        cur = sum(A)
        for i in range(K):
           # max_ = sum(A)
            min_ = min(A)
            idx = A.index(min_)
            A[idx] = -A[idx]
            max_ = sum(A)
        return max_
            


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        max_sum = -999999
        for _ in range(K):
            A = sorted(A)
            min_index = A.index(min(A))
            
            A[min_index] = -A[min_index]

            max_ = sum(A)
            # print(max_)
            # max_sum = max(max_sum, max_)
        return max_

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        while K > 0:
            min_index = A.index(min(A))
            A[min_index] = - A[min_index]
            K = K - 1
        
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        for i in range(K):
            
            val = min(A)
            
            #if val <= 0:
            A.remove(val)
            A.append(-1 * val)
                
           
                
        return sum(A)
                
               


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        while K != 0:
            A[A.index(min(A))] = -min(A)
            K -= 1
        return(sum(A))


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        c = 0
        
        while c < K:
            c += 1
            min_ = min(A)
            index = A.index(min_)
            A[index] = -1 * min_
        
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        while K>0:
            K-=1
            A[A.index(min(A))]=-min(A)
        return sum(A)

class Solution:
    import heapq
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        ## find the min element and its index and negate it K times
        
        ## Complexity = O(kn)
        
#         def findMin(A):
#             minValue = float('inf')
#             minIndex = 0

#             for i, ele in enumerate(A):
#                 if ele < minValue:
#                     minValue = ele
#                     minIndex = i
            
#             return minIndex

#         for k in range(K):
#             minIndex = findMin(A)
#             A[minIndex] = -A[minIndex]
            
        
        ### using min heap
        
        heapq.heapify(A)
        for k in range(K):
            A[0] = -A[0]
            heapq.heapify(A)
        
        return sum(A)
    
    ### let's do with heap, no need to pop just negate that element


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        for i in range(K) :
            check = min(A)
            t = A.index(check)
            A[t] = -A[t]
        
        return sum(A)
            
        
        
        
        


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for i in range(K):
            A[A.index(min(A))] *= -1
            
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        
        if not A: return sum(A)
        
        if K == 0: return sum(A)
        
        
        for i in range(K):
    
            A[A.index(min(A))] = - A[A.index(min(A))]
        
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        if not A:
            return sum(A)
        if K==0:
            return sum(A)
        for i in range(K):
            A[A.index(min(A))] = -A[A.index(min(A))]
        return sum(A)


# 5:47 ->
# Seems greedy: pick smallest number and flip it
class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        if K == 0:
            return sum(A)
        m = min(A)
        m_i = A.index(m)
        A[m_i] = -m
        return self.largestSumAfterKNegations(A, K - 1)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        for item in A :
            if item < 0 and K > 1:
                A[A.index(item)] = item * (-1)
                K-= 1
            elif item > 0 and K >= 2:
                K-=2
        else:
            A.sort()
            while K != 0:
                K -=1
                A[0] = A[0] * (-1)
        return sum(A)

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort()
        for i in range(K):
            A[0] = -1 * A[0]
            if A[0] > 0:
                A.sort()
        return sum(A)        

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        for i in range(K):
            A.sort()
            A[0] = -A[0]
        
        return sum(A)


class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        ans = sum(A)
        A.sort()
        
        for i in range(len(A)):
            if not K or A[i]==0:
                break
            if A[i]<0:
                ans -= 2*A[i]
                K-=1
            else:
                if K%2:
                    if i and A[i]>abs(A[i-1]):
                        ans += 2*A[i-1]
                    else:
                        ans -= 2*A[i]
                break
                    
        return ans