Skip to content

Instantly share code, notes, and snippets.

@abrarShariar
Last active October 12, 2021 18:38
Show Gist options
  • Save abrarShariar/f6c79821ca819e4a6b20abc70cf7f711 to your computer and use it in GitHub Desktop.
Save abrarShariar/f6c79821ca819e4a6b20abc70cf7f711 to your computer and use it in GitHub Desktop.
Get the maximum even sum of the K Elements
def get_max_even_sum (input_arr, k):
if k > len(input_arr) or len(input_arr) == 0:
return -1
even_arr = []
odd_arr = []
# sort the arr
input_arr.sort(reverse = True)
# separate out the even and odd arr
for i in range(len(input_arr)):
if input_arr[i]%2 == 0:
even_arr.append(input_arr[i])
else:
odd_arr.append(input_arr[i])
# take the max and keep track of the remaining
even_index, odd_index = 0, 0
max_sum = 0
# Go Greedy
# think about the case with only 1 or 2 element
# for 1:
# we must take the highest from the even Array
# for 2: we can either take (even + even = even) or (odd + odd = even)
# since even + odd is not equal to even
# we take max(current + next number) from even and odd array
while k > 0:
if k % 2 == 1:
if (len(even_arr) > 0):
max_sum += even_arr[even_index]
even_index += 1
k -= 1
else:
return -1
else:
if even_index < len(even_arr) - 1 and odd_index < len(odd_arr) - 1:
max_sum += max(even_arr[even_index] + even_arr[even_index + 1], odd_arr[odd_index] + odd_arr[odd_index + 1])
even_index += 2
odd_index += 2
elif even_index < len(even_arr) - 1:
max_sum += even_arr[even_index] + even_arr[even_index + 1]
even_index += 2
elif odd_index < len(odd_arr) - 1:
max_sum += odd_arr[odd_index] + odd_arr[odd_index + 1]
odd_index += 2
k -= 2
return max_sum
# Try these sample I/O:
# print(get_max_even_sum([4,2,6,7,8], 3))
# print(get_max_even_sum([1,1,1], 3))
# print(get_max_even_sum([1,1], 3))
# print(get_max_even_sum([1], 3))
# print(get_max_even_sum([1], 3))
# print(get_max_even_sum([], 0))
# print(get_max_even_sum([1,2], 1))
# print(get_max_even_sum([1,2], 2))
# print(get_max_even_sum([ 2, 4, 10, 3, 5 ], 3))
# print(get_max_even_sum([ 5,5,1,1,3 ], 3))
# print(get_max_even_sum([4,2,6,7,8], 3))
# print(get_max_even_sum([5, 5, 2, 4, 3], 3))
# print(get_max_even_sum([-1,-2,-2], 3))
# print(get_max_even_sum([1,2,4,11], 100))
# print(get_max_even_sum([1,2,4,11], 1))
# print(get_max_even_sum([5, 5, 1, 1, 3], 3))
@Shreeja7Sheth
Copy link

For this Example test: ([5, 6, 3, 4, 2], 5) it gives incorrect output: 14 whereas it should be 20... What can be corrected?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment