Greedy
Array
Sorting
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 <= 105
0 <= nums[i] <= 105
1 <= k <= nums.length
Solutions
Solution 1
Python3 Java C++ Go
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 )
}
GitHub