Maximum Sum Circular Subarray

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

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

918 Maximum Sum Circular SubarrayРазбор · 1×

Пример: [5, -2, -6, 3, -1, 4]. Обычный наибольший отрезок — [3, -1, 4] = 6, но ответ — отрезок через край: всё кольцо, 3, минус его наименьший отрезок [-2, -6] = -8.

nums051-22-6334-154hiHerehiloHerelototal5
этот шаготрезок, который суммирует hiHereотрезок, который суммирует loHere; в конце — вырезанная частьберём отсюдаответ: отрезок через край

total = 5: сумма всего кольца, пока только nums[0]

01/37
сначала · назад · пуск · шаг
Скорость
1function maxCircular(nums):
2 total = nums[0]
3 hiHere = nums[0] // largest run that ends at i
4 hi = nums[0]
5 loHere = nums[0] // smallest run that ends at i
6 lo = nums[0]
7 for i from 1 to len(nums) - 1:
8 total = total + nums[i]
9 hiHere = max(nums[i], hiHere + nums[i])
10 hi = max(hi, hiHere)
11 loHere = min(nums[i], loHere + nums[i])
12 lo = min(lo, loHere)
13 if hi < 0:
14 return hi // every number is negative
15 return max(hi, total - lo)
состояние
i
–
total
5
hiHere
–
hi
–
loHere
–
lo
–
историянажмите шаг, чтобы вернуться

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

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

  1. Лучший отрезок либо лежит внутри массива — его как hi находит обычный алгоритм Кадане, — либо идёт через край. Тогда оставшиеся числа образуют отрезок в середине, и чтобы взятая часть была наибольшей, оставшийся отрезок должен быть наименьшим: total - lo.
  2. Наименьший отрезок ищется так же, как наибольший, только через min вместо max, в том же проходе.
  3. Если все числа отрицательные, наименьший отрезок — всё кольцо, и total - lo = 0 означает «не брать ничего», а так нельзя. Тогда возвращаем hi — наибольшее отдельное число.

Сложность

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

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

Решить на LeetCode ↗

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