Сложность: 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 (чтобы учесть случай, когда все числа отрицательные).
😎 Решение:
def maxSubarraySumCircular(nums):
def kadane(arr):
current_sum = max_sum = arr[0]
for num in arr[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
max_kadane = kadane(nums)
total_sum = sum(nums)
min_kadane = kadane([-num for num in nums])
return max(max_kadane, total_sum + min_kadane if total_sum + min_kadane != 0 else max_kadane)
Ставь 👍 и забирай 📚 Базу знаний