Задача: 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 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int kadane(int[] arr) {
            int currentSum = arr[0], maxSum = arr[0];
            for (int i = 1; i < arr.length; i++) {
                currentSum = Math.max(arr[i], currentSum + arr[i]);
                maxSum = Math.max(maxSum, currentSum);
            }
            return maxSum;
        }

        int maxKadane = kadane(nums);
        int totalSum = 0;
        for (int num : nums) totalSum += num;
        int minKadane = kadane(Arrays.stream(nums).map(num -> -num).toArray());

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

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