Max Even Subset Sum
EasyGreedy · SalesForce
You are given a list of integers values. Choose any subset of them (each element used at most once, order does not matter) such that the sum of the chosen elements is even. The empty subset is allowed and has sum 0.
Return the largest even sum you can achieve.
Note that values may contain negative numbers and zeros. Since the empty subset is always available, the answer is never negative.
Example 1
- Input:
- values = [4, 7, 1, 2, 9]
- Output:
- 22
- Explanation
- All five values sum to 23, which is odd. Removing the smallest odd value,
1, gives22, the largest even total possible.
Example 2
- Input:
- values = [5, -1, 6]
- Output:
- 10
- Explanation
- The positives sum to
11. Dropping the5gives only6, but adding the-1fixes the parity at a cost of 1, giving10.
Example 3
- Input:
- values = [-2, -4, -7]
- Output:
- 0
- Explanation
- Every value would lower the total, so the best choice is the empty subset with sum
0.
Constraints
- 1 ≤
values.length≤ 105 - -109 ≤
values[i]≤ 109