-
Notifications
You must be signed in to change notification settings - Fork 13
/
FindMaxEvenSum.java
45 lines (39 loc) · 1.73 KB
/
FindMaxEvenSum.java
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
34
35
36
37
38
39
40
41
42
43
44
45
package by.andd3dfx.search;
/**
* Дано множество из N натуральных чисел.
* Необходимо выбрать его подмножество с максимальной четной суммой.
* Вывести эту сумму.
*
* @see <a href="https://youtu.be/GgZvAwyrAC0">Video solution</a>
*/
public class FindMaxEvenSum {
/**
* Очевидно, что в результат войдут ВСЕ четные числа исходного набора.
* А из нечетных - войдет их четное кол-во.
* Т.к. все числа натуральные, т.е. положительные, а нам нужна максимальная сумма -
* то из нечетных войдут все либо все кроме минимального.
* <p>
* В итоге решением будет одинарный проход по всем числам с поиском минимального нечетного числа и подсчетом суммы.
* Поток из суммы вычитаем это минимально нечетное, если сумма нечетная.
*/
public static int find(int[] a) {
int minOdd = -1;
int sum = 0;
for (int item : a) {
sum += item;
if (item % 2 == 1) {
if (minOdd == -1) {
minOdd = item;
continue;
}
if (item < minOdd) {
minOdd = item;
}
}
}
if (sum % 2 == 1) {
return sum - minOdd;
}
return sum;
}
}