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

Видео расскажет о том как решать задачи для собеседования в Google, Amazon, Apple, Microsoft, Facebook. Мы рассмотри задачу которая встречается при onsite интервью, данная задача с интервью является показателем умеете ли вы анализировать данные и находить в них закономерности

Скидка 50%, предложение действует до 1 августа.

Информация является частью одной из лекций курса Cronis

[aleksejpisarenkoo]

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

[pas]

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

[普京的手机]

А если в подотрезке должно быть не больше k элементов?

Я добавил строку:
if (r-l > k) nowSum -= a[l++]; // a это данный массив

Но этого недостаточно:

n=6, k=3
100 -10 -10 300 300 -10

Подобный алгоритм даст ответ 590 (верно 600)
Как дописать?

[HelloWorld-oceu]

При [-2, -1] или [-1]
Решение на видео не работает или я что-то неправильно написал)

class Solution {
public:
int maxSubArray(vector<int>& 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;
}
};

[nijatjafarguliyev]

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

[invisibleinvisible]

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

[trimmtrabb]

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

[romabulava]

не понял почему мы начинаем новый поиск, если первая сумма ушла в минус

[kseniiafilonenko]

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

[shurale]

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

[DenisBazhan]

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

[кириллпановицин]

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

[ГригорийКуклин-хт]

окей, а если у нас массив -1; -2; -3; -4; -5?

[lizarozantheva]

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

[manOfPlanetEarth]

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

Спасибо!

[klayx]

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