跳转至

2098. 长度为 K 的最大偶数和子序列 🔒

题目描述

给你一个整数数组 nums 和一个整数 k 。找出 nums 长度为 k 的所有子序列中的 最大偶数和 。
返回此总和，如果此总和不存在，则返回 -1。
子序列 是一个数组，可以通过删除一些元素或不删除任何元素而从另一个数组派生，而不改变其余元素的顺序。

 

示例 1：

输入: nums = [4,1,5,3,1], k = 3
输出: 12
解释:
具有最大可能偶数和的子序列是[4,5,3]。它的和为 4 + 5 + 3 = 12

示例 2:

输入: nums = [4,6,2], k = 3
输出: 12
解释:
具有最大可能偶数和的子序列是[4,6,2]。它的和为 4 + 6 + 2 = 12

示例 3:

输入: nums = [1,3,5], k = 1
输出: -1
解释:
长度为 1 的 NUM 的子序列没有偶数和。

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 105
  • 1 <= k <= nums.length

解法

方法一：贪心 + 排序

我们注意到，题目选取的是子序列，因此我们可以考虑先对数组进行排序。

接下来，我们先贪心地选取最大的 $k$ 个数，如果这些数的和为偶数，则直接返回这个和 $ans$。

否则，我们有两种贪心策略：

  1. 在最大的 $k$ 个数中，找到一个最小的偶数 $mi1$，然后在剩下的 $n - k$ 个数中，找到一个最大的奇数 $mx1$，将 $mi1$ 替换为 $mx1$，如果存在这样的替换，那么替换后的和 $ans - mi1 + mx1$ 一定是偶数；
  2. 在最大的 $k$ 个数中，找到一个最小的奇数 $mi2$，然后在剩下的 $n - k$ 个数中，找到一个最大的偶数 $mx2$，将 $mi2$ 替换为 $mx2$，如果存在这样的替换，那么替换后的和 $ans - mi2 + mx2$ 一定是偶数。

我们取最大的偶数和作为答案。如果不存在偶数和，则返回 $-1$。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def largestEvenSum(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = sum(nums[-k:])
        if ans % 2 == 0:
            return ans
        n = len(nums)
        mx1 = mx2 = -inf
        for x in nums[: n - k]:
            if x & 1:
                mx1 = x
            else:
                mx2 = x
        mi1 = mi2 = inf
        for x in nums[-k:][::-1]:
            if x & 1:
                mi2 = x
            else:
                mi1 = x
        ans = max(ans - mi1 + mx1, ans - mi2 + mx2, -1)
        return -1 if ans < 0 else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public long largestEvenSum(int[] nums, int k) {
        Arrays.sort(nums);
        long ans = 0;
        int n = nums.length;
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1];
        }
        if (ans % 2 == 0) {
            return ans;
        }
        final int inf = 1 << 29;
        int mx1 = -inf, mx2 = -inf;
        for (int i = 0; i < n - k; ++i) {
            if (nums[i] % 2 == 1) {
                mx1 = nums[i];
            } else {
                mx2 = nums[i];
            }
        }
        int mi1 = inf, mi2 = inf;
        for (int i = n - 1; i >= n - k; --i) {
            if (nums[i] % 2 == 1) {
                mi2 = nums[i];
            } else {
                mi1 = nums[i];
            }
        }
        ans = Math.max(ans - mi1 + mx1, ans - mi2 + mx2);
        return ans < 0 ? -1 : ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    long long largestEvenSum(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        long long ans = 0;
        int n = nums.size();
        for (int i = 0; i < k; ++i) {
            ans += nums[n - i - 1];
        }
        if (ans % 2 == 0) {
            return ans;
        }
        const int inf = 1 << 29;
        int mx1 = -inf, mx2 = -inf;
        for (int i = 0; i < n - k; ++i) {
            if (nums[i] % 2) {
                mx1 = nums[i];
            } else {
                mx2 = nums[i];
            }
        }
        int mi1 = inf, mi2 = inf;
        for (int i = n - 1; i >= n - k; --i) {
            if (nums[i] % 2) {
                mi2 = nums[i];
            } else {
                mi1 = nums[i];
            }
        }
        ans = max(ans - mi1 + mx1, ans - mi2 + mx2);
        return ans < 0 ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func largestEvenSum(nums []int, k int) int64 {
    sort.Ints(nums)
    ans := 0
    n := len(nums)
    for i := 0; i < k; i++ {
        ans += nums[n-1-i]
    }
    if ans%2 == 0 {
        return int64(ans)
    }
    const inf = 1 << 29
    mx1, mx2 := -inf, -inf
    for _, x := range nums[:n-k] {
        if x%2 == 1 {
            mx1 = x
        } else {
            mx2 = x
        }
    }
    mi1, mi2 := inf, inf
    for i := n - 1; i >= n-k; i-- {
        if nums[i]%2 == 1 {
            mi2 = nums[i]
        } else {
            mi1 = nums[i]
        }
    }
    ans = max(-1, max(ans-mi1+mx1, ans-mi2+mx2))
    if ans%2 < 0 {
        return -1
    }
    return int64(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function largestEvenSum(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let ans = 0;
    const n = nums.length;
    for (let i = 0; i < k; ++i) {
        ans += nums[n - i - 1];
    }
    if (ans % 2 === 0) {
        return ans;
    }
    const inf = 1 << 29;
    let mx1 = -inf,
        mx2 = -inf;
    for (let i = 0; i < n - k; ++i) {
        if (nums[i] % 2 === 1) {
            mx1 = nums[i];
        } else {
            mx2 = nums[i];
        }
    }
    let mi1 = inf,
        mi2 = inf;
    for (let i = n - 1; i >= n - k; --i) {
        if (nums[i] % 2 === 1) {
            mi2 = nums[i];
        } else {
            mi1 = nums[i];
        }
    }
    ans = Math.max(ans - mi1 + mx1, ans - mi2 + mx2);
    return ans < 0 ? -1 : ans;
}

评论