Задача: 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).

😎 Решение:

function maxSumDivThree($nums) {
    $totalSum = array_sum($nums);
    if ($totalSum % 3 == 0) {
        return $totalSum;
    }
    
    $mod1 = [];
    $mod2 = [];
    foreach ($nums as $num) {
        if ($num % 3 == 1) {
            $mod1[] = $num;
        } elseif ($num % 3 == 2) {
            $mod2[] = $num;
        }
    }
    
    sort($mod1);
    sort($mod2);
    
    if ($totalSum % 3 == 1) {
        $remove1 = empty($mod1) ? PHP_INT_MAX : $mod1[0];
        $remove2 = count($mod2) < 2 ? PHP_INT_MAX : $mod2[0] + $mod2[1];
        return $totalSum - min($remove1, $remove2);
    } else {
        $remove2 = empty($mod2) ? PHP_INT_MAX : $mod2[0];
        $remove1 = count($mod1) < 2 ? PHP_INT_MAX : $mod1[0] + $mod1[1];
        return $totalSum - min($remove2, $remove1);
    }
}

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