Python获取数组中k个元素的最大偶数和

Question

我一直在学习Python算法，想要解决的问题是：

1. 给定一个正整数数组A和一个整数K。
2. 在数组A中找到K个元素的最大偶数和。
3. 如果不可能，返回-1。

例如，如果有一个数组A=[1,2,3,4,4,5]，K=3， 则答案是12（5+4+3）， 这是具有K（3）个元素的最大偶数和。 然而，如果A=[3,3,3]并且K=1， 则答案是-1因为不能用一个元素组成偶数和。

我尝试从数组中排除每个最小的奇数，但当K=n时在while循环中失败了。 是否有任何简单的方法来解决这个问题？如果您能提供一些建议，我将非常感激。

- user14148536

---

你会发现如果使用递归，当重新检查new_A = [2, 3, 4, 4, 5]时，你可能会陷入无限循环。因此，你需要确保下一步已经减少了问题的规模，以避免这种情况的发生。 - Kenny Ostrom

Answer 1

对数组进行排序并“取出”最大的K个元素。

如果它已经是偶数总和-您就完成了。

否则，您需要替换一个元素，将您选择的偶数元素替换为您没有选择的奇数元素，或者反之亦然。您需要使两个元素之间的差异最小。

一种朴素的解决方案是检查所有可能的替换方式，但这是O(n^2)。你可以通过检查实际的两个可行候选者而做得更好:

• 您没有选择的最大奇数元素和您选择的最小偶数元素
• 您没有选择的最大偶数元素和您选择的最小奇数元素。

选择差异最小的那个。如果不存在这样的两个元素（即您的k=3、[3,3,3]的示例）- 没有可行的解决方案。

时间复杂度为O(nlogn)进行排序。

在我的（非常生疏的）Python中，应该是这样的：

def FindMaximalEvenArray(a, k):
    a = sorted(a)
    chosen = a[len(a)-k:]
    not_chosen = a[0:len(a)-k]
    
    if sum(chosen) % 2 == 0:
        return sum(chosen)
    
    smallest_chosen_even = next((x for x in chosen if x % 2 == 0), None)
    biggest_not_chosen_odd = next((x for x in not_chosen[::-1] if x % 2 != 0), None)    
    candidiate1 = smallest_chosen_even - biggest_not_chosen_odd  if smallest_chosen_even and biggest_not_chosen_odd else float("inf")

    smallest_chosen_odd = next((x for x in chosen if x % 2 != 0), None)
    biggest_not_chosen_even = next((x for x in not_chosen[::-1] if x % 2 == 0), None)
    candidiate2 = smallest_chosen_odd - biggest_not_chosen_even  if smallest_chosen_odd and biggest_not_chosen_even else float("inf")

    if candidiate1 == float("inf") and candidiate2 == float("inf"):
        return -1
    return sum(chosen) - min(candidiate1, candidiate2)

注意：这可以做得更好（从时间复杂度的角度出发），因为你并不真正关心所有元素的顺序，只需要找到“候选项”和前K个元素。因此，你可以使用选择算法而不是排序，这样就可以在O(n)时间内完成。

- amit