https://www.hackerrank.com/challenges/max-array-sum/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dynamic-programming

https://leetcode.com/problems/house-robber/

Она же, но в другой обертке? Прикольно

Она же, но в другой обертке? Прикольно

На хакерранке значится как медиум. Я считаю это фигня: везде где без дп не решить без тайм лимита — это хард.

Там еще интересный вариант есть, когда дома кольцом стоят, а не вдоль улицы

Думаю не на много сложнее будет

Там еще интересный вариант есть, когда дома кольцом стоят, а не вдоль улицы

Типа надо ещё учитывать связь последнего и первого?

Давно у нас медленный режим?)

Давно у нас медленный режим?)

Она же, но в другой обертке? Прикольно

Сильно мешает? Я поставил тротл чтобы ограничивать поток однострочных сообщений, проще поправить свой прошлый текст. Но если мешает могу убрать, давай ревью :-)

Не думал, что так быстро догадаюсь как пофиксить

Не думал, что так быстро догадаюсь как пофиксить

Не думал, что так быстро догадаюсь как пофиксить

Вот ты тоже делаешь оптимизацию по памяти из-за которой не фига не понять суть решения 😅

Оптимизацию? Там же O(1)

Вот именно. А если держать два вектора хоть как-то ещё можно объяснить решение. Иначе магия.

Ааа, щас объясню почему нам не нужны вектора

Мне интересно как можно додуматься до О(1) не пройдя вариант с дополнительной памятью сначала.

Не признаный гений. Шучу, я же решал Литкодовскую задачу про грабителей, а эта очень похожа

Нормальная тема. Я хочу в идеале в разборах задач стремиться к последовательному переходу к оптимальному решению. Не люблю эти посты на литкоде типа “beats 99%”, открываешь — а там криптокод, хз в чем идея.

Нормальная тема. Я хочу в идеале в разборах задач стремиться к последовательному переходу к оптимальному решению. Не люблю эти посты на литкоде типа “beats 99%”, открываешь — а там криптокод, хз в чем идея.

Пхаха, ну я щас объясню) У вас решение такое же кстати, только dp1[i-1] с dp2[i-1], путает немного, т.к. кажется что работаем с один и тем же числом, под индексом i-1, а на самом деле это i-1 и i-2

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

По сути у нас одинаковые решения) Просто вы храните все результаты

А когда люди с листа пишут с двумя переменными — это колдунство.

Может есть у кого идеи, как поправить?

А когда люди с листа пишут с двумя переменными — это колдунство.

Хорошего отдыха. Под вечер самое-то

Какой там отдых, я качаю тут всех 🙈

Объясняю про грабителей сначала (где только положительные числа): У нас каждое число есть вариант: брать или не брать, я предлагаю БРАТЬ каждый раз (`sum1 + n`), но в случае чего отказываться от предыдущего результата (`sum2 - prev + n`). т.е. 3+ раза НЕ брать нам никогда не выгодно (только положительные в это задачке), т.е. у нас будет такие ситуации: 0) Пропускать 0 раз нам запрещено, это было бы просто суммой всех элементов 1) Пропускаем 1 раз. Мы постоянно чередуем, т.е. идет игра на повышение (1,2,3,4,5 – каждый раз хотим сбросить предыдущий и взять новый, но тогда нам надо будет чередовать **ВСЕГО 2 СУММЫ**) 2) Пропускаем 2 раза. Мы *обрезаем* наши предыдущие результаты, нам не важно что было до этого, у нас идут числа 100 1 1 100 (т.е. нам единички вообще не надо брать), в этом случае sum1 == sum2 def maxSubsetSum(arr): sum1 = sum2 = prev = 0 for n in arr: sum1 = max(sum2 - prev + n, sum1 + n) sum1, sum2 = sum2, sum1 prev = n return max(sum1, sum2)

С отрицательными числами все тоже самое, только мы можем пропускать больше 2 раз, т.к. мы не хотим прибовлять отрицательные числа max( , , sum1), + т.к. мы пропускает, то надо делать предыдущий элемент 0, т.е. prev = max(n, 0)

По-людски объяснил.

Мне девушка говорит что за 2 года я так и не научился общаться с людьми))0) Мне очень сложно что-либо объяснять

Просто с какого-то уровня — объяснять это прямо фултайм работа. Порой «программируешь» в гуглодоках.

Ну а что, это так устроено. Много ли Джефф Дин программирует? Мне кажется только для себя, на литкод раз в неделю заходит 😄

Да я понимаю, управлять персоналом всегда выгоднее чем работать. Кончено работать можно как 100 программистов, но в итоге руководить и управлять 200стами, выгоднее. Или управлять 50ю, чтобы каждый работал как 3

Ну, я не думаю, что он руководит сотнями программистов. Скорее десятками и находится очень близко к реальному проекту. Такой вариант меня вполне устраивает.

А еще выгодно руководить теми, кто руководит программистами

В фангах есть плюс в том, что инженерный трек может быть практически таким же выгодным, как управленческий.

В фангах есть плюс в том, что инженерный трек может быть практически таким же выгодным, как управленческий.

Имеешь в виду горизонтальное и вертикальное развитие?

Имеешь в виду горизонтальное и вертикальное развитие?

“Born in Madurai, India, Pichai earned his degree from the Indian Institute of Technology Kharagpur in metallurgical engineering. Moving to the United States, he attained an M.S. from Stanford University in materials science and engineering”

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

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

Короче оканчивал на инжинере по металам, а окончил управлением самой огромной компание программистов

Вот как ему пригодилось образование 😹

"Диплом не нужен!" (с) 😄