Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

Если немного изменить код, то должно работать

function getMaxSubSum(arr) {
  var maxCurrent = maxGlobal = arr[0];
  for (var i = 1; i < arr.length; i++) {
    maxCurrent = Math.max(arr[i], maxCurrent + arr[i]);
    maxGlobal = Math.max(maxGlobal, maxCurrent);
  }
  return maxGlobal;
}

Тут без проверки на пустой массив, но суть ясна :)

Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

Он не работает если массив целиком состоит из отрицательных чисел, вместо минимального числа он вернет 0.

Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

В алгоритме Кадана тоже ошибка.

Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

А нет, был не прав :) Ответ найден.

Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

Предлагал самый настоящий бинарный, с делением каждый раз на 2 :)
Просто невнимательно прочитал условия задачи и пропустил самое главное — что яиц всего два.
Тут получается первое яйцо кидаем каждые 10 этажей, как разбилось то второе кидаем через этаж с последнего «целого» десятка.
Медленнее бинарного поиска, но целее будут яйца.

Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

И последний, это алгоритм кадана или что-то есть лучше?

Выпуск#4: ITренировка — актуальные вопросы и задачи от ведущих компаний

С яйцами решить «бинарным поиском» не лучший вариант?

Дайджест свежих материалов из мира фронтенда за последнюю неделю №287 (30 октября — 5 ноября 2017)

Есть большое приложение на первой ветке, переписывать его нет желания.