Java | LeetCode
Задача: 1262. Greatest Sum Divisible by Three
Сложность: medium
Если задан целочисленный массив nums, верните максимально возможную сумму элементов массива, которая делится на три.
Пример:
Input: nums = [3,6,5,1,8]
Output: 18
👨💻 Алгоритм:
1⃣Найдите сумму всех элементов массива.
2⃣Если сумма делится на 3, то она и есть ответ.
3⃣Если сумма при делении на 3 дает остаток 1, удалите один элемент с остатком 1 или два элемента с остатком 2 (если их сумма равна 2).
Если сумма при делении на 3 дает остаток 2, удалите один элемент с остатком 2 или два элемента с остатком 1 (если их сумма равна 2).
😎 Решение:
import java.util.Arrays;
public class Solution {
public int maxSumDivThree(int[] nums) {
int totalSum = Arrays.stream(nums).sum();
if (totalSum % 3 == 0) {
return totalSum;
}
int mod1Min = Integer.MAX_VALUE;
int mod2Min = Integer.MAX_VALUE;
int[] mod1Min2 = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
int[] mod2Min2 = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
for (int num : nums) {
if (num % 3 == 1) {
if (num < mod1Min2[1]) {
mod1Min2[1] = num;
Arrays.sort(mod1Min2);
}
} else if (num % 3 == 2) {
if (num < mod2Min2[1]) {
mod2Min2[1] = num;
Arrays.sort(mod2Min2);
}
}
}
int result = 0;
if (totalSum % 3 == 1) {
result = totalSum - mod1Min2[0];
if (mod2Min2[0] != Integer.MAX_VALUE && mod2Min2[1] != Integer.MAX_VALUE) {
result = Math.max(result, totalSum - mod2Min2[0] - mod2Min2[1]);
}
} else if (totalSum % 3 == 2) {
result = totalSum - mod2Min2[0];
if (mod1Min2[0] != Integer.MAX_VALUE && mod1Min2[1] != Integer.MAX_VALUE) {
result = Math.max(result, totalSum - mod1Min2[0] - mod1Min2[1]);
}
}
return result;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 419 ·