Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]
Output: 3

👨‍💻 Алгоритм:

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

function maxSubarraySumCircular($nums) {
    function kadane($arr) {
        $currentSum = $arr[0];
        $maxSum = $arr[0];
        for ($i = 1; $i < count($arr); $i++) {
            $currentSum = max($arr[$i], $currentSum + $arr[$i]);
            $maxSum = max($maxSum, $currentSum);
        }
        return $maxSum;
    }

    $maxKadane = kadane($nums);
    $totalSum = array_sum($nums);
    $nums = array_map(function($num) { return -$num; }, $nums);
    $minKadane = kadane($nums);

    return max($maxKadane, $totalSum + $minKadane == 0 ? $maxKadane : $totalSum + $minKadane);
}

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