Интервью Google. Нахождение подмассива с максимальной суммой. Алгоритм Sliding Window

Видео расскажет о том как решать задачи для собеседования в Google, Amazon, Apple, Microsoft, Facebook. Мы рассмотри задачу которая встречается при onsite интервью, данная задача с интервью является показателем умеете ли вы анализировать данные и находить в них закономерности
О курсе: cronis.by/about-online-class/
Скидка 50%, предложение действует до 1 августа.
Оценка сложности алгоритмов: • Оценка сложности алгор...
Информация является частью одной из лекций курса Cronis

[@koruffvfx]

Классная задача, встретилась на codewars. Были проблемы с пониманием, чего от меня хотят. Начал искать, наткнулся на видео, и все стало предельно понятно. Спасибо за такое объяснение!

[@invisibleinvisible83]

Ребят, а кто на собесы не так давно ходил, какие еще задачи на какие темы дают? Кроме дизайн паттерн интервью, лайфкода? Спасибо за видео.

[@Igor_Kash]

Спасибо!😊

[@kseniiafilonenko955]

Как решить такую же задачу только не с суммой, а произведением?

[@user-lt1we3wh7n]

Здравствуйте. Скажите, пожалуйста, в какой программе вы сделали такую красивую презентацию.

[@Cronis]

Добрый вечер! В PowerPoint

[@trimmtrabb7629]

Я единственное не уловил момент, где вы ввели maxSum (не maxSumRange, а именно maxSum). Откуда она берется?

[@Cronis]

Maxsum - это текущая максимальная сумма. Это просто поле в объекте max sum range

[@nijatjafarguliyev]

Очень класный канал! Автор суперски объясняет. Только почему так мало просмотров и подписчиков?

[@manOfPlanetEarth]

ну, и слава богу. конкуренция не нужна.

[@manOfPlanetEarth]

Нормас. Но двойная рекурсия в задаче про стабильное перемешивание 2х массивов на недостижимом уровне. Спасибо!

[@DenisBazhan]

17 сентября начало? Что нужно для покупки за 800 студент?

[@Cronis]

Все верно, начало 17го сентября. Для получения цены 800 рублей, необходимо иметь действующий студенческий билет

[@lizarozantheva4737]

На каким языке программирования написан код?

[@Cronis]

На Java. Но это псевдокод, он будет работать везде

[@pas777777]

Не указано только, что используется алгоритм Кадане...а в остальном всё нормально)

[@Cronis]

Возможно, не знаю его) Это просто скользящее окно, где оно неверно, когда сумма меньше нуля. Не думал, что это какой-то специальный алгоритм)

[@shurale85]

Скажите, пожалуйста, а зачем сдвигать начальный индекс подмассива, если текущая сумма оказалась меньше нуля? Ведь двигая просто конечный индекс мы тоже получаем очередной подмассив. И в этом случаи получается уде совсем непростая задачка. И самый примитивный способ это перебрать всевозможные подмассивы для каждого элемента

[@Cronis]

Иначе не найти ответ. Сложность все равно будет линейной, так как мы каждый раз, находя отрицательную сумму, подвигаем левый указатель скользящего окна вперёд

[@user-br4gt7xu2j]

@@Cronis а если все числа массива отрицательные, то этот алгоритм не подходит, ибо currSum будет всегда отрицательный и сброс его до нуля нивелирует процесс, если только не допустить решения с нулевым подмассивом, что абсурдно, ведь необходимо найти хоть какой-то существующий подмассив, удовлетворяющий условию в рамках заданного массива, а не просто ответить что решение: "ничего"

[@Cronis]

Проверьте, все будет работать. А потом напишите почему :)

[@shurale85]

@@Cronis так, с этим я разбирался годом ранее и видимо благополучно забыл. Опять возникает это вопрос: нужно ли все таки тратить время на вот такого радо задачи?))

[@miraage]

@@shurale85 оно то работает, если условие задачи разрешает возвращать подмассив размером 1. Задача куда интереснее, если подмассив обязан содержать минимум 2 элемента, при условии, что исходный массив содержит минимум 3 элемента.

[@HelloWorld-oc2eu]

При [-2, -1] или [-1] Решение на видео не работает или я что-то неправильно написал) class Solution { public: int maxSubArray(vector& nums) { int maxSumSubArray = 0; int currentSumSubArray = 0; int windowStart = 0; int windowEnd; for (windowEnd = 0; windowEnd < nums.size(); ++windowEnd) { currentSumSubArray += nums.at(windowEnd); if (currentSumSubArray > maxSumSubArray) maxSumSubArray = currentSumSubArray; if (currentSumSubArray < 0) { currentSumSubArray = 0; windowStart = windowEnd + 1; } } return maxSumSubArray; } };

[@HelloWorld-oc2eu]

а без скольязщего окна получилось решить, но это скорее решение в лоб int maxSubArray(vector& nums) { int currentSum = 0; int maxSum = nums[0]; for(int i = 0 ; i < nums.size(); i++){ currentSum += nums[i]; maxSum = std::max(maxSum,currentSum); if (currentSum < 0 ) currentSum = 0; } return maxSum; }

[@klayx2728]

Не рассмотрен случай, если все числа отрицательные

[@Cronis]

Попробуйте запустить со всеми отрицательными :)

[@learpcss9569]

Для случая если все числа отрицательные - подмассив с длиной 0 будет самым наилучшим вариантом, что и учитывается в данном алгоритме

[@manOfPlanetEarth]

Ну, ты разобрался?? Вернётся подмассив, состоящий из одного максимального отрицательного элемента исходного массива.

[@klayx2728]

@@manOfPlanetEarth я уже не помню, что тут, и вспоминать не хочу. Скорее всего, разобрался

[@manOfPlanetEarth]

@@klayx2728 Понял:) Если не секрет, может сказать, пригодились ли тебе эти видео и стал ли заниматься чем-то релевантным с этими видео (например, программированием)?