Maximum Subarray

Средняя№53лучший подмассив

Дан массив целых чисел, среди них есть отрицательные. Выбери отрезок из одного или нескольких соседних чисел с наибольшей суммой и верни эту сумму. Наш пример: [3, -4, 2, -1, 5, -7, 4] — ответ 6, отрезок [2, -1, 5].

53 Maximum SubarrayРазбор · 1×

Пример: [3, -4, 2, -1, 5, -7, 4]. Смотрите на индекс 2: отрезок [3, -4] за ним даёт -1, поэтому его бросают и начинают новый с 2.

numsherebest031-4223-1455-7643
этот шаготрезок, который суммирует hereберём отсюдаотброшены новым началомответ

Отрезок, который кончается в индексе 0, может быть только [3]: here = 3

01/27
сначала · назад · пуск · шаг
Скорость
1function maxSubArray(nums):
2 here = nums[0] // best sum of a run that ends at i
3 best = nums[0]
4 for i from 1 to len(nums) - 1:
5 if here < 0:
6 here = nums[i] // start over
7 else:
8 here = here + nums[i]
9 best = max(best, here)
10 return best
состояние
i
–
here
3
best
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Лучший отрезок, который кончается в индексе i, — это либо одно nums[i], либо nums[i], добавленное к лучшему отрезку, который кончается в i - 1. Других вариантов нет, поэтому одно число here несёт всё нужное слева.
  2. Отрезок за спиной с отрицательной суммой только уменьшает всё, что после него, поэтому отрезок начинается заново. С суммой 0 или больше он не мешает, поэтому отрезок растёт.
  3. Каждый отрезок где-то кончается, поэтому наибольшее here по всем индексам, которое хранит best, и есть ответ. best начинается с nums[0], а не с 0, так что массив из одних отрицательных чисел тоже получит своё наибольшее число.

Сложность

Время O(n): один проход, на каждое число постоянная работа. Память O(1): только here и best; строки на рисунке лишь показывают их историю.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.