Задача: 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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний