Задача с собеседования в Blinkit

Дан целочисленный массив nums. Найдите подмассив с наибольшей суммой и верните эту сумму.

Follow up: если вы нашли решение с асимптотикой O(n), попробуйте реализовать ещё одно, используя метод "разделяй и властвуй".

Пример 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: Подмассив [4,-1,2,1] имеет наибольшую сумму, равную 6.

Пример 2:
Input: nums = [1]
Output: 1
Explanation: Подмассив [1] имеет наибольшую сумму, равную 1.

Пример 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: Подмассив [5,4,-1,7,8] имеет наибольшую сумму, равную 23.

Ограничения:
1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение за O(n):
Классический алгоритм для этой задачи - алгоритм Кадана, где для каждого эл-та решаем:
- продлить эл-том текущий подмассив или начать новый подмассив с этого эл-та.
- параллельно обновляем глобальный максимум, если сумма текущего подмассива больше.

Разберём подробнее:
max_sum - глобальный максимум; инициализируем, как float("-inf"), гарантируя, что первый эл-т массива обновит максимум;
cur_sum - текущая сумма подмассива; инициализируем, как 0 (пустой префикс).

Проходим по массиву:
- формула, обновляющая cur_sum, выбирает: начать новый подмассив с текущего эл-та или продлить существующий. Если накопленная сумма отрицательна, значит, любой подмассив, начинающийся до текущего эл-та и идущий дальше, будет иметь сумму меньше, чем если бы он начинался с текущего эл-та => выгодно начать новый подмассив;
- обновляем глобальный максимум, выбирая максимальное значение среди max_sum и cur_sum.

Сложность
O(n) - по времени (проходим по массиву один раз)
O(1) - по памяти (храним две переменные)

Код
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = float("-inf")
cur_sum = 0

for num in nums:
cur_sum = max(num, cur_sum + num)
max_sum = max(max_sum, cur_sum)

return max_sum


Подход "разделяй и властвуй":
Идея: делим массив пополам. Подмассив с наибольшей суммой попадает в один из трёх случаев:
- находится в левой половине;
- в правой половине;
- пересекает середину (начинается в левой половине и заканчивается в правой).

Рекурсивная функция принимает границы текущего подмассива [left, right], при первом вызове - весь массив:
База: если left == right - подмассив из одного эл-та, возвращаем его.

Рекурсивное ветвление:
1. Находим середину mid;
2. Рекурсивно ищем максимум в левой [left, mid] и правой половине [mid + 1, right];
3. Ищем максимум, пересекающий mid:
- идём влево от mid до left, накапливая текущую сумму; ищем cross_left - максимальный суффикс левой половины.
- идём от mid+1 вправо до right, накапливая текущую сумму; ищем cross_right - максимальный префикс правой половины.
- вычисляем cross_max, как сумму cross_left и cross_right.
4. Находим максимум среди left_max, right_max и cross_max.

Сложность:
O(n log n) - по времени (T(N) = 2T(N/2) + O(N) = O(N log N), где 2T(N/2) - рекурсивные вызовы для левой и правой половин и O(N) - проход от left до right для вычисления cross_max)
O(log n) - по памяти (глубина стека рекурсии)

Код:
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def divide_and_conquer(left: int, right: int) -> int:
if left == right:
return nums[left]

mid = (left + right) // 2
left_max = divide_and_conquer(left, mid)
right_max = divide_and_conquer(mid + 1, right)

cross_left = float("-inf")
cur_sum = 0
for i in range(mid, left - 1, -1):
cur_sum += nums[i]
cross_left = max(cross_left, cur_sum)

cross_right = float("-inf")
cur_sum = 0
for i in range(mid + 1, right + 1):
cur_sum += nums[i]
cross_right = max(cross_right, cur_sum)

cross_max = cross_left + cross_right

return max(left_max, cross_max, right_max)

return divide_and_conquer(0, len(nums) - 1)

@algoses