Last active
October 12, 2021 18:38
-
-
Save abrarShariar/f6c79821ca819e4a6b20abc70cf7f711 to your computer and use it in GitHub Desktop.
Get the maximum even sum of the K Elements
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
For this Example test: ([5, 6, 3, 4, 2], 5) it gives incorrect output: 14 whereas it should be 20... What can be corrected?