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

Source: leetcode | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms

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:
		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:
		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)
				elif 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:
		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:
		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)
		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:
		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:
		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:
		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 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:
		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