Description#
You are given an integer array nums and an integer k. Find the largest even sum of any subsequence of nums that has a length of k.
Return this sum, or -1 if such a sum does not exist.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [4,1,5,3,1], k = 3
Output: 12
Explanation:
The subsequence with the largest possible even sum is [4,5,3]. It has a sum of 4 + 5 + 3 = 12.
Example 2:
Input: nums = [4,6,2], k = 3
Output: 12
Explanation:
The subsequence with the largest possible even sum is [4,6,2]. It has a sum of 4 + 6 + 2 = 12.
Example 3:
Input: nums = [1,3,5], k = 1
Output: -1
Explanation:
No subsequence of nums with length 1 has an even sum.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1051 <= k <= nums.length
Solutions#
Solution 1#
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 % 2 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(-1, Math.max(ans - mi1 + mx1, ans - mi2 + mx2));
return ans % 2 != 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 % 2 || 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)
}
|
