Given an array of integers of size N and a number K., You must modify array arr[] exactly K number of times. Here modify array means in each operation you can replace any array element either arr[i] by -arr[i] or -arr[i] by arr[i]. You need to perform this operation in such a way that after K operations, the sum of the array must be maximum.
Example 1:
Input:
N = 5, K = 1
arr[] = {1, 2, -3, 4, 5}
Output:
15
Explanation:
We have k=1 so we can change -3 to 3 and
sum all the elements to produce 15 as output.
Example 2:
Input:
N = 10, K = 5
arr[] = {5, -2, 5, -4, 5, -12, 5, 5, 5, 20}
Output:
68
Explanation:
Here  we have k=5 so we turn -2, -4, -12 to
2, 4, and 12 respectively. Since we have
performed 3 operations so k is now 2. To get
maximum sum of array we can turn positive
turned 2 into negative and then positive
again so k is 0. Now sum is
5+5+4+5+12+5+5+5+20+2 = 68
Your Task:
You don't have to print anything, printing is done by the driver code itself. You have to complete the function maximizeSum() which takes the array A[], its size N, and an integer K as inputs and returns the maximum possible sum.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N,K ≤ 10^{5}
-10^{9} ≤ A_{i} ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def maximizeSum(self, a, n, k):

        # Your code goes here

Solutions:
import heapq

class Solution:

	def maximizeSum(self, a, n, k):
		heapq.heapify(a)
		for i in range(k):
			val = heapq.heappop(a)
			heapq.heappush(a, -1 * val)
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		while k > 0 and i < n and (a[i] < 0):
			a[i] *= -1
			i += 1
			k -= 1
		return sum(a) - k % 2 * min(a) * 2


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		while i < n and k > 0:
			if a[i] < 0:
				a[i] = -a[i]
				k -= 1
			else:
				break
			i += 1
		if k > 0 and k % 2 != 0:
			min_abs = min(a)
			a[a.index(min_abs)] = -min_abs
		sum_arr = sum(a)
		return sum_arr


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		for i in range(n):
			if a[i] < 0 and k > 0:
				a[i] = a[i] * -1
				k -= 1
		a.sort()
		while k > 0:
			a[0] *= -1
			k -= 1
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		neg = []
		pos = []
		r = []
		for i in range(n):
			if a[i] < 0:
				neg.append(a[i])
			else:
				pos.append(a[i])
		neg.sort()
		pos.sort()
		if k <= len(neg):
			for i in range(k):
				neg[i] *= -1
			r += neg
			r += pos
		else:
			for i in range(len(neg)):
				neg[i] *= -1
			if (k - len(neg)) % 2 == 0:
				r += neg
				r += pos
			else:
				pos += neg
				pos.sort()
				pos[0] *= -1
				r += pos
		return sum(r)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		ans = sum(a)
		i = 0
		while i < n and k > 0:
			if a[i] < 0:
				a[i] = -a[i]
				k -= 1
			i += 1
		total = sum(a)
		mini = min(a)
		if k % 2 == 0:
			return total
		else:
			return total - 2 * mini


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		Sum = 0
		i = 0
		while k > 0 and i < n:
			if a[i] < 0:
				a[i] = -1 * a[i]
				k = k - 1
			i += 1
		a.sort()
		if k % 2 == 0:
			return sum(a)
		else:
			a[0] = -1 * a[0]
			return sum(a)


import math

class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		for i in range(n):
			if a[i] < 0 and k > 0:
				a[i] = -1 * a[i]
				k -= 1
		if k == 0 or k % 2 == 0:
			return sum(a)
		a.sort()
		a[0] = -1 * a[0]
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		for i in range(n):
			if a[i] < 0:
				a[i] = -a[i]
				k -= 1
				if k == 0:
					break
		ans = sum(a)
		mini = min(a)
		if k % 2 != 0:
			return ans - 2 * mini
		return ans


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		ok = k
		last = 0
		for i in range(n):
			if a[i] < 0:
				a[i] = -a[i]
				last = i
				k -= 1
				if k == 0:
					break
			else:
				break
		if k > 0:
			if k % 2:
				if last + 1 < n and a[last + 1] == 0:
					last += 1
				else:
					a[last] = -a[last]
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		prev_num = None
		smallest_neg = 99999999
		smallest_pos = 99999999
		res = 0
		if a[-1] < 0:
			smallest_neg = a[-1]
		for i in a:
			if i < 0 and k > 0:
				res += i * -1
				k -= 1
			elif k > 0:
				if prev_num == None:
					smallest_pos = i
				elif prev_num < 0:
					smallest_neg = prev_num
					smallest_pos = i
				res += i
			else:
				res += i
			prev_num = i
		if k > 0 and k % 2 != 0:
			smallest_num = min(abs(smallest_neg), smallest_pos)
			res -= smallest_num * 2
		return res


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		index = 0
		op = 0
		for n_op in range(k):
			if a[index] < 0:
				a[index] = -1 * a[index]
				index += 1
				index %= n
				op += 1
			else:
				break
		a.sort()
		if op < k:
			for n_op in range(k - op):
				a[0] = -1 * a[0]
				op += 1
		_sum = 0
		if op == k:
			for _index in range(n):
				_sum += a[_index]
		return _sum


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		j = 0
		ans = 0
		while i < k and j < n - 1 and (a[j] < 0):
			a[j] = -a[j]
			i += 1
			j += 1
		while i < k:
			a[j] = -a[j]
			i += 1
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		num = 0
		while True:
			if num == k:
				break
			elif i < n and a[i] < 0:
				a[i] = -a[i]
				num += 1
			elif (k - num) % 2 != 0:
				index = a.index(min(a))
				a[index] = -a[index]
				break
			else:
				break
			i += 1
		return sum(a)


class Solution:

	def maximizeSum(self, arr, n, k):
		arr.sort()
		i = 0
		while i < n and k > 0:
			if arr[i] < 0:
				arr[i] = arr[i] * -1
				k -= 1
			i += 1
		arr.sort()
		while k > 0:
			arr[0] = arr[0] * -1
			k -= 1
		return sum(arr)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		for i in range(n):
			if k == 0:
				break
			elif a[i] < 0:
				a[i] = -1 * a[i]
				k -= 1
		idx = a.index(min(a))
		if k % 2 != 0:
			a[idx] = -1 * a[idx]
		s = sum(a)
		return s


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		c = 0
		for i in a:
			if i < 0:
				c = c + 1
		if c == 0:
			if k % 2 == 0:
				return sum(a)
			else:
				a[0] = -a[0]
				return sum(a)
		t = 0
		for i in range(0, len(a)):
			if a[i] < 0:
				a[i] = -a[i]
				t = t + 1
				if t == k:
					break
		a.sort()
		if t != k:
			A = k - t
			n = A % 2
			if n == 0:
				return sum(a)
			else:
				a[0] = -a[0]
				return sum(a)
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		idx = 0
		a.sort()
		while k > 0 and idx < n and (a[idx] < 0):
			a[idx] = abs(a[idx])
			k -= 1
			idx += 1
		if k % 2 == 1:
			if idx == 0:
				a[0] = -a[0]
			elif idx == n:
				a[-1] = -a[-1]
			elif abs(a[idx - 1]) <= abs(a[idx]):
				a[idx - 1] = -a[idx - 1]
			else:
				a[idx] = -a[idx]
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		idx = 0
		numberOfNegatives = 0
		for num in a:
			if num < 0:
				numberOfNegatives += 1
		a.sort()
		while k > 0 and idx < n and (a[idx] < 0):
			a[idx] = abs(a[idx])
			k -= 1
			idx += 1
		if k % 2 == 1:
			if idx == 0:
				a[0] = -a[0]
			elif idx == n:
				a[-1] = -a[-1]
			elif abs(a[idx - 1]) <= abs(a[idx]):
				a[idx - 1] = -a[idx - 1]
			else:
				a[idx] = -a[idx]
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		j = 0
		while i < k and i < n and (a[j] < 0):
			a[j] = -1 * a[j]
			j += 1
			i += 1
		rem = k - i
		a.sort()
		if rem > 0:
			if rem % 2 == 0:
				ans = sum(a)
				return ans
			else:
				a[0] = -1 * a[0]
				return sum(a)
		return sum(a)


def maximize_arr_sum(arr: [], n, k):
	arr = sorted(arr)
	count = 0
	for i in range(0, n):
		if count == k:
			break
		if arr[i] < 0:
			count = count + 1
			arr[i] = arr[i] * -1
	if count == k:
		return sum(arr)
	arr = sorted(arr)
	left_count = k - count
	if left_count % 2 != 0:
		arr[0] = arr[0] * -1
	return sum(arr)

class Solution:

	def maximizeSum(self, a, n, k):
		return maximize_arr_sum(a, n, k)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		while k > 0 and i < n:
			if a[i] < 0:
				a[i] = -a[i]
				k -= 1
			i += 1
		if k % 2 != 0:
			val = min(a)
			indx = a.index(val)
			a[indx] = -a[indx]
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		while i < n and a[i] < 0 and k:
			a[i] = -a[i]
			i += 1
			k -= 1
		if k == 0 or k % 2 == 0:
			return sum(a)
		else:
			m = a[0]
			mi = 0
			for i in range(1, n):
				if a[i] < m:
					m = a[i]
					mi = i
			a[mi] = -a[mi]
			return sum(a)


class Solution:

	def maximizeSum(self, arr, n, k):
		arr.sort()
		num = k
		for (i, ele) in enumerate(arr):
			if ele < 0 and num:
				arr[i] = ele * -1
				num -= 1
		t = sum(arr)
		if num % 2 == 1:
			t -= 2 * min(arr)
		return t


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		j = 0
		while k > 0:
			if a[j] < 0:
				a[j] = -a[j]
				k -= 1
				j += 1
				if j > n - 1:
					j = 0
			else:
				if k % 2 == 1:
					a.sort()
					a[0] = -a[0]
				k = 0
		sum = 0
		for item in a:
			sum += item
		return sum


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		for i in range(n):
			if a[i] < 0 and k > 0:
				a[i] = abs(a[i])
				k -= 1
			if k == 0:
				break
		a.sort()
		if k % 2 != 0:
			a[0] = -a[0]
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		pcount = 0
		ncount = 0
		a.sort()
		for i in range(n):
			if a[i] < 0:
				ncount += 1
			else:
				pcount += 1
		i = 0
		while ncount > 0 and k > 0:
			a[i] = -a[i]
			ncount -= 1
			k -= 1
			i += 1
		a.sort()
		if k > 0:
			while k > 0:
				x = a[0]
				a[0] = -x
				k -= 1
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		neg = 0
		zero = 0
		pos = 0
		ans = 0
		for i in a:
			if i == 0:
				zero += 1
			elif i < 0:
				neg += 1
			else:
				pos += 1
		i = 0
		temp = k
		while k > 0 and i < n:
			if a[i] < 0:
				a[i] *= -1
				k -= 1
				i += 1
			else:
				break
		ans = sum(a)
		if zero > 0 or neg >= temp or (temp - neg) % 2 == 0:
			return ans
		else:
			mini = a[0]
			for i in a:
				if i < 0:
					mini = min(mini, -1 * i)
				else:
					mini = min(mini, i)
			return ans - 2 * mini


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		cn = 0
		for i in range(min(k, n)):
			if a[i] < 0:
				a[i] = -1 * a[i]
				cn = cn + 1
		if k <= n and (k - cn) % 2 == 1:
			a[cn] = -1 * a[cn]
		if k > n and (k - cn) % 2 == 1:
			a.sort()
			a[0] = -1 * a[0]
		return sum(a)


class Solution:

	def maximizeSum(self, arr, n, k):
		arr.sort()
		c = 0
		for i in range(len(arr)):
			if arr[i] < 0 and k > 0:
				arr[i] = abs(arr[i])
				c += 1
				k -= 1
		s = sum(arr)
		mn = min(arr)
		if k % 2 == 1:
			s -= 2 * mn
		return s


class Solution:

	def maximizeSum(self, arr, n, k):
		arr.sort()
		for i in range(0, n):
			if arr[i] < 0 and k > 0:
				arr[i] = -arr[i]
				k -= 1
		tsum = sum(arr)
		smallest = min(arr)
		if k & 1:
			tsum -= 2 * smallest
		return tsum


class Solution:

	def maximizeSum(self, a, n, k):
		a = sorted(a, key=lambda x: abs(x), reverse=True)
		i = 0
		while i < n:
			if k <= 0:
				return sum(a)
			if a[i] < 0 and k > 0:
				a[i] = -1 * a[i]
				k -= 1
			i += 1
		a = sorted(a)
		while k > 0:
			a[0] = -1 * a[0]
			k -= 1
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		count = 0
		for i in range(min(n, k)):
			if a[i] < 0:
				a[i] = abs(a[i])
				count += 1
		if count == k or (k - count) % 2 == 0:
			return sum(a)
		else:
			return sum(a) - 2 * min(a)


class Solution:

	def maximizeSum(self, a, n, k):
		arr = a
		arr.sort()
		for i in range(n):
			if arr[i] > 0 or k == 0:
				break
			else:
				arr[i] = abs(arr[i])
				k -= 1
		arr.sort()
		if k > 0 and k % 2 == 0:
			return sum(arr)
		elif k > 0 and k % 2 != 0:
			arr[0] = -arr[0]
			return sum(arr)
		else:
			return sum(arr)


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		c = 0
		for i in a:
			if i < 0:
				c += 1
		if c > k:
			i = 0
			j = 0
			while j < k and i < n:
				if a[i] < 0:
					a[i] = -1 * a[i]
					j += 1
				i += 1
			return sum(a)
		else:
			i = 0
			while i < c:
				if a[i] < 0:
					a[i] = -1 * a[i]
				i += 1
			a.sort()
			if (k - i) % 2 == 0:
				return sum(a)
			else:
				return sum(a) - 2 * a[0]


class Solution:

	def maximizeSum(self, a, n, k):
		a.sort()
		i = 0
		cor = 0
		while k:
			if i == n or a[i] >= 0:
				cor = -(k % 2) * min(a)
				break
			else:
				a[i] = -a[i]
				k -= 1
			i += 1
		return sum(a) + 2 * cor


import heapq

class Solution:

	def maximizeSum(self, a, n, k):
		heapq.heapify(a)
		while k:
			mini = heapq.heappop(a)
			heapq.heappush(a, -mini)
			k -= 1
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		maxsum = 0
		a.sort()
		temp = 0
		while temp < n and a[temp] <= 0 and k:
			maxsum += -a[temp]
			temp += 1
			k -= 1
		if k % 2 == 1:
			if temp <= n and k + temp <= n:
				if abs(a[temp - 1]) < a[temp]:
					maxsum -= 2 * abs(a[temp - 1])
				else:
					a[temp] = -a[temp]
			elif temp == 0:
				maxsum -= 2 * abs(a[temp])
			else:
				maxsum -= 2 * abs(a[temp - 1])
		for i in range(temp, n):
			maxsum += a[i]
		return maxsum


import heapq

class Solution:

	def maximizeSum(self, a, n, k):
		heapq.heapify(a)
		for _ in range(k):
			x = heapq.heappop(a)
			heapq.heappush(a, -x)
		return sum(a)


class Solution:

	def maximizeSum(self, a, n, k):
		a = sorted(a)
		count = 0
		for i in a:
			if i < 0:
				count += 1
		i = 0
		while i < count and k > 0:
			if a[i] < 0:
				a[i] = -a[i]
				k -= 1
				i += 1
		if k % 2 == 0:
			return sum(a)
		else:
			g = a.index(min(a))
			a[g] = -a[g]
			return sum(a)