остановил на 8:07, пишу примерное свое решение. в целом еще до пояснений стало понятно, что могут быть отрицательные числа, 0 и от 0 до 1. Дальнейшие размышления: нам надо для каждого следующего числа проверять в какой диапазон он попадает и в зависимости от этого применять знак. Для начала забываю про то, что формируемый результат может быть отрицательным. Главное увеличивать число, положительный знак попробую выставить правильным количеством операций. По идее, если на отрицательные числа умножать/делить четное количество раз, то все будет хорошо) Тогда: 0 как правило лучше прибавлять/отнимать (одно и тоже), на числа от 0 до 1 (не включительно) и от 0 до -1 делить, 1 прибавлять, -1 отнимать (либо использовать для корректировки знака). на те, что >1 и
Интересная задача. Тоже поймал себя на greedy не учитывая constrains, но об этом нужно сразу уточнять. По факту наличия минуса в голову пришло хранить в массиве, но это не оптимально, так как дает пространственно линейную сложность. Остаётся выход использовать переменную для константной сложности.
в такой ситуации все тоже самое, только сначала считаем количество отрицательных чисел, если четное то при отрицательном числе умножение, если нечетное то перед отрицательным числом умножение, но перед последним отрицательным числом минус. Проходя по массиву можно просто считать количество отрицательный@@persssotami
@@persssotami Просто в голос хохочу с таких организмов, которые указывают кому-либо на ошибки и при этом демонстрируют собственную безграмотность... вдвойне смешнее, когда такие типы говорят о том, что что-то *неправильно* и при этом даже не знают как *правильно* это слово пишется 😂😂😂
До просмотра решения. Возможно в алгоритме сделать условие поведения в зависимости от 4х цифр: 1) есть ли 0 2) есть ли числа от 0 до 1 и в зависимости от того какой индекс конкретного числа
А я подумал, что мы можем брать любые соседние элементы массива, применять к ним операцию, а затем записывать новый элемент вместо этих двух. То есть не обязательно идти по порядку: на любом шаге берём любые a[i] и a[i+-1] (рядом стоящие элементы), получаем new_elem посредством применения определённой операции к a[i] и a[i+-1], кладём его на i-ое место, а[i] и a[i+-1] удаляем. Такая задача была бы сильно сложнее, хотя возможно, это и подразумевалось.
Первое что в голову пришло это пройтись циклом и вложенными тернарнеми операторами соблюсти условия на ноль и отрицательные числа 🤔 Посмотрим теперь какое решение😅 Мда, условие нужны от i = -1 то +, еще и знаки учесть нужно, потом n += i или n *= i. По производительности конечно нужно проверить. После просмотра видео пришла еще мысль запустить цикл, переменная n равна первому числу. Потом берем в каждой итерации цикла четыре переменные полученые с разными знаками и присваиваем максимальное полученное значение n = Max(x1, Max(x2, Max(x3, x4))). Так пробегаем по массиву.
*Видео на паузе* **насколько понял из условия - вывод должен быть максимальным значением, без необходимости сохранять последовательность знаков а также массив нельзя сортировать и нужно работать лишь с исходным создаём два счётчика Проходим по массиву и сохраняем: 1) количество отрицательных чисел в первый счётчик, если оно чётное - ставим булевую переменную можноУмножитьДваждыНаМинус - true, else false 2) количество отрицательных чисел > -1 во второй счётчик, если оно чётное - ставим булевую переменную можноДелитьДваждыНаМинус - true, else false - создаём 2 временные переменных типа double для числ массива [temporary1] [temporary2] - создаём 2 переменных типа double для результата, куда будем записывать два варианта промежуточных действий и сравнивать их [result1] [result2] проверяем что массив содержит больше 1го элмента и записываем первый элемент в [temporary1] иначе сразу выводим его Заходим в цикл (начинаем с первого индекса, не нулевого) проходим заново по массиву, записывая i во временную переменные -> [temporary2] заходим в проверки: 1) Если [temporary2] == 0 { суммируем / вычитаем два временных элемента, без разницы результат сразу записываем в temporary1; continue; } 2) Если [temporary2] > 0 { суммируем и перемножаем [temporary1] [temporary2] записывая в [result1] [result2]; сравниваем [result1] [result2] и записываем большее значение в [temporary1]; continue; } 3) Если [temporary2] < 0 && > -1 если можноДелитьДваждыНаМинус == true { делим и вычитаем [temporary1] [temporary2] записывая в [result1] [result2]; сравниваем [result1] [result2] и записываем большее значение в [temporary1]; continue; } else { вычитаем [temporary1] [temporary2] результат сразу записываем в temporary1; continue; } 4) Если [temporary2] < 0 если можноУмножатьДваждыНаМинус == true { умножаем и вычитаем [temporary1] [temporary2] записывая в [result1] [result2]; сравниваем [result1] [result2] и записываем большее значение в [temporary1]; } else вычитаем [temporary1] [temporary2] результат сразу записываем в temporary1; выходим из цикла return temporary1; не кидайтесь тапками если совсём всё плохо... я только начал учиться:) upd: досмотрел видео.. выше всё плохо( надо было не сравнивать в моменте 2 результата а плюсом вычислить минимальный и вести их оба к концу массива
Писал код на питоне, пока не смотрел продолжение, но написал довольно быстро, не верится что задача такая простая… (это не Хейт, наоборот, уважение автору за разминку для мозгов!!🤝) Логика следующая: Брать каждую пару чисел в массиве (за счет цикла for) и находить максимальный результат действий с ними (для этого написал функцию, только надо учесть что числа могут быть 0.0, в функции результаты всех действий беру в массив и возвращаю максимальное число), а после результат подставляю на место второго числа в паре, чтобы дальше идти по циклу. После окончания цикла ответом будет последнее число в массиве, оно же - максимальное АПД: очень круто, я понял в хитрость задачи, я в гугл не прошел 😂😂
Выбор крайних положительных и отрицательных называется максимальное по модулю. Насчет абсолютной безошибочности представленного решения есть сомнения, потому что максимальное число, которое можно получить это 151, а не 150. (-5*-3/0.1+1), либо я неверно понял ограничения в условии задачи и числа нужно перебирать именно в заданном порядке, иначе я бы решал воспользовавшись предварительной сортировкой с последующим применением априорных знаний о свойствах чисел и операций.
Ну это простая задача, линейный алгоритм с одним проходом. Нам нужно сохранять два массива операций, некое ветвление, когда попадается отрицательное число, а наш сумматор положительный, ибо, если он отрицательный, вычисляем, что будет больше, вычесть минус (для сумматора близкого к нулю) или умножить но новое отрицательное и получить большее положительное. Как только оно попалось, в первом массиве храним "безопасный вариант" с вычитанием, а параллельно сохраняем вариант с умножением и переходом в минус для сумматора. Как только нам попалось еще одно отрицательное, его домножаем и делаем второй вариант решения основным, а если до конца массива минусов больше не попалось, то исходный безопасный остается. Для чисел меньше 1 по модулю делаем деление, ну и для отрицательных так, как выше было описано, только с заменой умножения на деление. Если попадается ноль, то просто ставим плюс. Теперь посмотрим видео дальше, что же ты предлагаешь :) Кстати, звук очень тихий, либо надо прямо в микрофон говорить, либо усиление громкости сделать...
5:50 - так мы ищем максимум как результат всех операций, или мы должны вернуть такую последовательность операций, которые дадут максимальный результат? Если второе, то у нас сложность по памяти O(N)
Задача довольно простая (уровня Medium на Leetcode). Линейный проход по массиву. Не верю что это задача на 200к. Разве что на первых этапах собеседования. Вот если бы тут соблюдался приоритет операций - поверил бы, да, это сложнее гораздо.
Вопрос. При инициализации массива mins , maxs , нужно их заполнить всеми значениями первого элемента, иначе при начальных данных array[0]=0 ,array[1]=0, будет ошибка, т.к. четвертое значение не определено . или в яве не будут эти ячейки проверятся?
Поставил на паузу, подумал несколько минут. Кажется, это задача на дерево. Каждый узел имеет 4 ветви(+, -, /, *). Обходим дерево, отсекая каждый раз 2 из 4 ветвей. Нас интересует максимум положительный и минимум отрицательный (потому что на следующих этапах можно умножить или разделить на другое отрицательное число). Довольно интересная, но несложная задача. Вначале она кажется сложнее, чем есть. Я думал над матрицей решений, в зависимости от текущего значения и следующего числа (от минус бесконечности до -1, от -1 до нуля, нуль, от нуля до 1, от единицы до плюс бесконечности), но этот подход не будет давать оптимального решения, если нужно дважды умножить на отрицательное число, чтобы получить максимум. Поэтому я решил представить себе полный перебор (ребята, всегда начинайте с тупого и неэффективного решения, оно лучше, чем ничего). А это просто dfs, и его можно соптимизировать, как я написал выше. О, а ведь можно и дальше пойти в оптимизации, если делать обход в ширину, и хранить отрицательный минимум и положительный максимум для всего уровня, а не только для текущего узла, тогда углубление будет только в 2 ветви.
Досмотрел, убедился, что я молодец😄 Нюанс в том, что собеседование в гугл - это, во-первых, стресс, во-вторых, лотерея. Я свои собесы не то чтобы завалил, задачи были даже проще, чем я ожидал(кроме одной), но не дотянул то тут, то там. Времени действительно дают очень мало, всего час, из него минус минут 10-15 на разговор вначале и в конце, и при этом надо было решить 2 задачи каждый раз. Но все вполне реально, хоть и непросто. пару месяцев на литкоде, пара книжек, несколько лет опыта в индустрии, немного везения, и вот она, «работа мечты». Кстати, 200к это в США же, в Европе разве столько base дают, или это TC? Автору спасибо, зрителям удачи😉
Решение последнего примера сделано неверно. В первых вычислениях получилось число -0,33, Влад его зачеркнул. Но если мы умножим 0,1 на -0,33, то получится -0,033. Дальше делим -5 на -0,033 и уже получается 151,52 примерно. Этот ответ уже больше того, который получился способом Влада. Думаю, что там возможны и другие хитрости, которые я не рассмотрел. Так что решение Влада не даёт самого-самого максимального ответа, особенно если в массиве много дробных чисел. Забавно, что сам Влад постоянно упоминал про нюансы с дробями, но не учёл их
Так а почему вы поменяли числа местами и делите -5 на -0,033? Чтобы получить максимум с дробями, нужно большее число разделить на маленькое, т.е. стратегия получения максимума остается верной
по условию нельзя -5 делить на -0.033 -5 последнее число в массиве, можно только делать действия с ним вторым номером: умножить / отнять / поделить / сложить -> и тут максимальное значение будет -0.033 * (-5) = 0.165
Тоже испытываю постоянную нужду рисовать схемки для лучшего понимания. Пока обхожусь листочком/карандашиком. Но иногда надо объяснять не только себе, но и другим. Поэтому вопрос: какой планшет и какую программу/сайт посоветуете для рисования чего-то подобного этому видео?
Есть вопрос: если проставить действия сразу?: то тогда даже с первым набором цифр, результат другой если считать по правилам математики: типа умножение первое делать... если считать отдельно каждый раз пошагово так сказать может стоить прописать условия для операций: А) если число 0, то /; (но тут надо добавить неравенство - если оба числа меньше ед... типа, чтобы деление было больше сложения и еще условие для отриц. чисел... тоже проверить)б) если число 1, то +; в) если одно число (+) положит, а другое (-) отриц., то * или -; г) если число = 0, то + (чтобы не занулять результат) ; д) если оба положительные, то *; и е) если оба числа отрицательные, то *. Тогда вообще легко: действия отсеиваются сразу...
А в чем проблема? Больше единицы - умножаем. Меньше единицы - делим. Отрицательные - прибавляем. Если пройти предварительно, то можно понять будет ли четность отрицательных. Если будет четность, то только умножаем и делим
можно поробовать накапливать результат выражения и применяя каждую операцию проверять стало ли накопленное число больше, если меньше, то другая операция и так до конца массива
Владос лучший ! Если не сложно , ответь на вопрос . Развиваюсь в сфере аналитики и мне интересно знать , как в FAANG обстоят дела с данным направлением , либо может поделишься где можно узнать информацию насчет аналитических направлений в биг тех ?
1. Хранить последное число в переменную last_num 2. Проделать все операции с последним и текущим числом 3. Получить максимальное число из полученных результатов, и хранить в переменную max_num 4. Установить max_num в last_num P.S: Не учел отрицательные числа)
Не могу понять, почему с ифами будет дольше, чем второй вариант Можно же изначально пройти по массиву, посмотреть сколько чисел отрицательных Затем снова идем по массиву возможны следующие ситуации: 1) Число > 1: умножаем на него 2) число 0 < 1: делим на него 3) число = 1: прибавляем 4) число = 0: прибавляем 5) число -1 < 0: если отрицательных четное количество, то делим, иначе вычитаем 6) число = -1: вычитаем 7) число < -1: если количество отрицательных четное, то умножаем, иначе вычитаем Неужели 7 ифов будут дольше?
Ифами надо учитывать что у нас в аккумуляторе лежит. Например, [0,2 и 1.5] - здесь лучше сложить, а не умножить. И быстрее будет вычислить сумму и произведение и их сравнить, чем делать сравнения-вычисления чтобы понять, какую операцию выбрать. Ифы годятся чтобы совсем уж бесперспективные операции не выполнять, вроде деления в примере выше.
Довольно плохое решение я считаю, но 1)отсортировать массив 2)и проходясь по циклу ставим на все возможные варианты условия(например если меньше единицы и больше -1 прибавляем или отнимаем, а если меньше -1 умножаем или ой чет запутался ) Знаю что очень плохое решение, но это то что пришло в голову в первую очередь Смотрю дальше!
Как насчет этого варианта решения? double[] nums = {1,-3,0.1,-5}; Arrays.sort(nums); double max; for (int i = 1; i < nums.length; i++) { max = nums[i-1]*nums[i]; double d = nums[i - 1] / nums[i]; double sum = nums[i - 1] + nums[i]; double minus = nums[i - 1] - nums[i]; if(d > max) max=d; else if(sum > max) max = sum; else if(minus > max) max = minus; nums[i] = max; } System.out.println(nums[nums.length-1]); И здесь во втором примере же ответ должен же быть 151? Или по условии задачи последовательность чисел в массиве нельзя менять?
Понял. Если это умножение на любое число, то оно не рождает новый min или max(деление можно представить в виде умножения: 1 деленное на это число) . Сложение не рождает новый min или max (вычитание можно представить в виде сложения такого же числа с другим знаком)
А обязательно ли брать всн числа в массиве последовательно. Во втором примере видно, что если нарушить последовательность, можно получить больший результат
Константы не учитываются, потому что n может быть бесконечно большим в сравнении с единицей. Поэтому постоянные величины всегда можно опускать для сокращения записи
Отличный ролик, спасибо за труд. (далее будет мой вариант кода) Писал код до предоставления Владом решения Написал на python за ~20 минут, если не трудно подскажите как улучшить. Заранее спасибо from random import randint as r array = [] while len(array) < 30: array.append(r(-500, 500)/r(-500, 500)) summ = array[0] count_of_negative_values = 0 if count_of_negative_values % 2 == 0: for i in array[1:]: if i > 0: summ += max((summ + i), (summ * i), (summ / i)) else: summ += max(-(summ * i), -(summ / i)) else: worse_negative_value = float('-0.' + '0' * 100 + '1') for n in array: if n < 0: count_of_negative_values += 1 if max((-10 * n), (-10 / n)) < max((-10 * worse_negative_value), (-10 / worse_negative_value)): worse_negative_value = n for i in array[1:]: if i > 0: summ += max((summ + i), (summ * i), (summ / i)) elif i != worse_negative_value: summ += max(-(summ * i), -(summ / i)) else: summ -= worse_negative_value print(summ)
[-0.9862700228832952, -0.8229166666666666, -1.9513888888888888, 3.8515625, -2.904255319148936] у вас получается (-2.13) а у автора (42.06) итог - не работает
Я бы просто насрал if, if else и с позором завершил собес
Влад, шикарное видео! Делай, пожалуйста, как можно больше разборов таких задач! будем лайкать каждое видео!!
Очень интересно. Такие видео с разбором задач пожалуй лучший контент)
Топ контент! Ушел решать задачу))
Спасибо что делишься такой важной инфой для нас)
остановил на 8:07, пишу примерное свое решение. в целом еще до пояснений стало понятно, что могут быть отрицательные числа, 0 и от 0 до 1.
Дальнейшие размышления: нам надо для каждого следующего числа проверять в какой диапазон он попадает и в зависимости от этого применять знак.
Для начала забываю про то, что формируемый результат может быть отрицательным. Главное увеличивать число, положительный знак попробую выставить правильным количеством операций. По идее, если на отрицательные числа умножать/делить четное количество раз, то все будет хорошо) Тогда:
0 как правило лучше прибавлять/отнимать (одно и тоже),
на числа от 0 до 1 (не включительно) и от 0 до -1 делить,
1 прибавлять, -1 отнимать (либо использовать для корректировки знака).
на те, что >1 и
Спасибо за Ваш труд! Коммент в поддержку канала.
Влад, вы просто супер мастер, это потрясающе, я восхищена
Спасибо,полезное и заряжающее видео,в прочем как обычно)❤️
Поставил на паузу в начале видео. Решил эту задачу. Меня не учили лучшие преподаватели по алгоритмам из лучших бигтех компаний
Очень полезное видео. Хотелось бы больше видео такого формата
Интересная задача. Тоже поймал себя на greedy не учитывая constrains, но об этом нужно сразу уточнять. По факту наличия минуса в голову пришло хранить в массиве, но это не оптимально, так как дает пространственно линейную сложность. Остаётся выход использовать переменную для константной сложности.
Проход по массиву за n
Дальше конструкции иф , елсе иф, елсе с проверками: 1 число отрицательное - знак минус, =1 или =0 - знак плюс, 0
Не правильно, если что
[4.0, -2.0, -5.0] выдаст 11,
а ожидалось 40.0
в такой ситуации все тоже самое, только сначала считаем количество отрицательных чисел, если четное то при отрицательном числе умножение, если нечетное то перед отрицательным числом умножение, но перед последним отрицательным числом минус. Проходя по массиву можно просто считать количество отрицательный@@persssotami
@@persssotami Просто в голос хохочу с таких организмов, которые указывают кому-либо на ошибки и при этом демонстрируют собственную безграмотность... вдвойне смешнее, когда такие типы говорят о том, что что-то *неправильно* и при этом даже не знают как *правильно* это слово пишется 😂😂😂
Крутой контент! Продолжай!💪
До просмотра решения. Возможно в алгоритме сделать условие поведения в зависимости от 4х цифр:
1) есть ли 0
2) есть ли числа от 0 до 1
и в зависимости от того какой индекс конкретного числа
спасибо, классное видео и интересная задача
Интересная задача на подумать, теперь хочется ее на Python сделать 👍
Супер ролик, спасибо
А я подумал, что мы можем брать любые соседние элементы массива, применять к ним операцию, а затем записывать новый элемент вместо этих двух. То есть не обязательно идти по порядку: на любом шаге берём любые a[i] и a[i+-1] (рядом стоящие элементы), получаем new_elem посредством применения определённой операции к a[i] и a[i+-1], кладём его на i-ое место, а[i] и a[i+-1] удаляем. Такая задача была бы сильно сложнее, хотя возможно, это и подразумевалось.
Ну да, вариант у тебя более наглядный с точки зрения кода, его будет проще понять тому, кто будет потом разбираться. Согласен.
Первое что в голову пришло это пройтись циклом и вложенными тернарнеми операторами соблюсти условия на ноль и отрицательные числа 🤔 Посмотрим теперь какое решение😅
Мда, условие нужны от i = -1 то +, еще и знаки учесть нужно, потом n += i или n *= i.
По производительности конечно нужно проверить.
После просмотра видео пришла еще мысль запустить цикл, переменная n равна первому числу. Потом берем в каждой итерации цикла четыре переменные полученые с разными знаками и присваиваем максимальное полученное значение n = Max(x1, Max(x2, Max(x3, x4))). Так пробегаем по массиву.
*Видео на паузе*
**насколько понял из условия - вывод должен быть максимальным значением, без необходимости сохранять последовательность знаков
а также массив нельзя сортировать и нужно работать лишь с исходным
создаём два счётчика
Проходим по массиву и сохраняем:
1) количество отрицательных чисел в первый счётчик, если оно чётное - ставим булевую переменную можноУмножитьДваждыНаМинус - true, else false
2) количество отрицательных чисел > -1 во второй счётчик, если оно чётное - ставим булевую переменную можноДелитьДваждыНаМинус - true, else false
- создаём 2 временные переменных типа double для числ массива [temporary1] [temporary2]
- создаём 2 переменных типа double для результата, куда будем записывать два варианта промежуточных действий и сравнивать их [result1] [result2]
проверяем что массив содержит больше 1го элмента и записываем первый элемент в [temporary1]
иначе сразу выводим его
Заходим в цикл (начинаем с первого индекса, не нулевого)
проходим заново по массиву, записывая i во временную переменные -> [temporary2]
заходим в проверки:
1) Если [temporary2] == 0
{
суммируем / вычитаем два временных элемента, без разницы результат сразу записываем в temporary1;
continue;
}
2) Если [temporary2] > 0
{
суммируем и перемножаем [temporary1] [temporary2] записывая в [result1] [result2];
сравниваем [result1] [result2] и записываем большее значение в [temporary1];
continue;
}
3) Если [temporary2] < 0 && > -1
если можноДелитьДваждыНаМинус == true
{
делим и вычитаем [temporary1] [temporary2] записывая в [result1] [result2];
сравниваем [result1] [result2] и записываем большее значение в [temporary1];
continue;
}
else
{
вычитаем [temporary1] [temporary2] результат сразу записываем в temporary1;
continue;
}
4) Если [temporary2] < 0
если можноУмножатьДваждыНаМинус == true
{
умножаем и вычитаем [temporary1] [temporary2] записывая в [result1] [result2];
сравниваем [result1] [result2] и записываем большее значение в [temporary1];
}
else
вычитаем [temporary1] [temporary2] результат сразу записываем в temporary1;
выходим из цикла
return temporary1;
не кидайтесь тапками если совсём всё плохо... я только начал учиться:)
upd: досмотрел видео.. выше всё плохо(
надо было не сравнивать в моменте 2 результата а плюсом вычислить минимальный и вести их оба к концу массива
Писал код на питоне, пока не смотрел продолжение, но написал довольно быстро, не верится что задача такая простая… (это не Хейт, наоборот, уважение автору за разминку для мозгов!!🤝)
Логика следующая:
Брать каждую пару чисел в массиве (за счет цикла for) и находить максимальный результат действий с ними (для этого написал функцию, только надо учесть что числа могут быть 0.0, в функции результаты всех действий беру в массив и возвращаю максимальное число), а после результат подставляю на место второго числа в паре, чтобы дальше идти по циклу.
После окончания цикла ответом будет последнее число в массиве, оно же - максимальное
АПД: очень круто, я понял в хитрость задачи, я в гугл не прошел 😂😂
Точно так же решил 😅
Ахуенный видос, продолжай в том же духе 🔥
Очень интересно спасибо. Разбор очень крутой все понятно)
Выбор крайних положительных и отрицательных называется максимальное по модулю. Насчет абсолютной безошибочности представленного решения есть сомнения, потому что максимальное число, которое можно получить это 151, а не 150. (-5*-3/0.1+1), либо я неверно понял ограничения в условии задачи и числа нужно перебирать именно в заданном порядке, иначе я бы решал воспользовавшись предварительной сортировкой с последующим применением априорных знаний о свойствах чисел и операций.
Условие задачи, что операции выполняются последовательно по массиву, без скобок и приоритетности, нельзя массив сортировать
Ну это простая задача, линейный алгоритм с одним проходом. Нам нужно сохранять два массива операций, некое ветвление, когда попадается отрицательное число, а наш сумматор положительный, ибо, если он отрицательный, вычисляем, что будет больше, вычесть минус (для сумматора близкого к нулю) или умножить но новое отрицательное и получить большее положительное. Как только оно попалось, в первом массиве храним "безопасный вариант" с вычитанием, а параллельно сохраняем вариант с умножением и переходом в минус для сумматора. Как только нам попалось еще одно отрицательное, его домножаем и делаем второй вариант решения основным, а если до конца массива минусов больше не попалось, то исходный безопасный остается. Для чисел меньше 1 по модулю делаем деление, ну и для отрицательных так, как выше было описано, только с заменой умножения на деление. Если попадается ноль, то просто ставим плюс. Теперь посмотрим видео дальше, что же ты предлагаешь :) Кстати, звук очень тихий, либо надо прямо в микрофон говорить, либо усиление громкости сделать...
Очень простая.
Скучно дальше смотреть,
Или там есть ограничение на число строк в процедуре?
5:50 - так мы ищем максимум как результат всех операций, или мы должны вернуть такую последовательность операций, которые дадут максимальный результат?
Если второе, то у нас сложность по памяти O(N)
Задача довольно простая (уровня Medium на Leetcode). Линейный проход по массиву. Не верю что это задача на 200к. Разве что на первых этапах собеседования. Вот если бы тут соблюдался приоритет операций - поверил бы, да, это сложнее гораздо.
Сразу видно кто после курсов по пайтону 😅
@@ukr9760 При чем тут пайтон? Я если что C++ разраб. Да и в данном случае язык принципиальной роли играет в решении данной задачи от слова совсем.
Блин, какие все вокруг умные! Мне страшно даже…(
@@benjaminBTNне смотри на других, смотри на себя
@@nurmashfg8858 легко сказать. Человек- существо социальное
Топчик!
Вопрос. При инициализации массива mins , maxs , нужно их заполнить всеми значениями первого элемента, иначе при начальных данных array[0]=0 ,array[1]=0, будет ошибка, т.к. четвертое значение не определено . или в яве не будут эти ячейки проверятся?
Поставил на паузу, подумал несколько минут.
Кажется, это задача на дерево. Каждый узел имеет 4 ветви(+, -, /, *). Обходим дерево, отсекая каждый раз 2 из 4 ветвей. Нас интересует максимум положительный и минимум отрицательный (потому что на следующих этапах можно умножить или разделить на другое отрицательное число). Довольно интересная, но несложная задача. Вначале она кажется сложнее, чем есть. Я думал над матрицей решений, в зависимости от текущего значения и следующего числа (от минус бесконечности до -1, от -1 до нуля, нуль, от нуля до 1, от единицы до плюс бесконечности), но этот подход не будет давать оптимального решения, если нужно дважды умножить на отрицательное число, чтобы получить максимум. Поэтому я решил представить себе полный перебор (ребята, всегда начинайте с тупого и неэффективного решения, оно лучше, чем ничего). А это просто dfs, и его можно соптимизировать, как я написал выше.
О, а ведь можно и дальше пойти в оптимизации, если делать обход в ширину, и хранить отрицательный минимум и положительный максимум для всего уровня, а не только для текущего узла, тогда углубление будет только в 2 ветви.
Досмотрел, убедился, что я молодец😄
Нюанс в том, что собеседование в гугл - это, во-первых, стресс, во-вторых, лотерея. Я свои собесы не то чтобы завалил, задачи были даже проще, чем я ожидал(кроме одной), но не дотянул то тут, то там. Времени действительно дают очень мало, всего час, из него минус минут 10-15 на разговор вначале и в конце, и при этом надо было решить 2 задачи каждый раз.
Но все вполне реально, хоть и непросто. пару месяцев на литкоде, пара книжек, несколько лет опыта в индустрии, немного везения, и вот она, «работа мечты».
Кстати, 200к это в США же, в Европе разве столько base дают, или это TC?
Автору спасибо, зрителям удачи😉
Решение последнего примера сделано неверно. В первых вычислениях получилось число -0,33, Влад его зачеркнул. Но если мы умножим 0,1 на -0,33, то получится -0,033. Дальше делим -5 на -0,033 и уже получается 151,52 примерно. Этот ответ уже больше того, который получился способом Влада. Думаю, что там возможны и другие хитрости, которые я не рассмотрел. Так что решение Влада не даёт самого-самого максимального ответа, особенно если в массиве много дробных чисел. Забавно, что сам Влад постоянно упоминал про нюансы с дробями, но не учёл их
Так а почему вы поменяли числа местами и делите -5 на -0,033?
Чтобы получить максимум с дробями, нужно большее число разделить на маленькое, т.е. стратегия получения максимума остается верной
по условию нельзя -5 делить на -0.033
-5 последнее число в массиве, можно только делать действия с ним вторым номером: умножить / отнять / поделить / сложить -> и тут максимальное значение будет -0.033 * (-5) = 0.165
то есть можно просто прорешать наиболее частые задачи или даже заучить и попасть на высокую позицию?
Первое что пришло в голову - перебор всех вариантов. По ресурсам не очень хорошо, зато работать будет
Тоже испытываю постоянную нужду рисовать схемки для лучшего понимания. Пока обхожусь листочком/карандашиком. Но иногда надо объяснять не только себе, но и другим. Поэтому вопрос: какой планшет и какую программу/сайт посоветуете для рисования чего-то подобного этому видео?
Есть вопрос: если проставить действия сразу?: то тогда даже с первым набором цифр, результат другой если считать по правилам математики: типа умножение первое делать... если считать отдельно каждый раз пошагово так сказать может стоить прописать условия для операций: А) если число 0, то /; (но тут надо добавить неравенство - если оба числа меньше ед... типа, чтобы деление было больше сложения и еще условие для отриц. чисел... тоже проверить)б) если число 1, то +; в) если одно число (+) положит, а другое (-) отриц., то * или -; г) если число = 0, то + (чтобы не занулять результат) ; д) если оба положительные, то *; и е) если оба числа отрицательные, то *. Тогда вообще легко: действия отсеиваются сразу...
В расчёт также надо брать и наиболее близкие к 0, а не только min/max . Как вам 1 /- 0.00000001
А в чем проблема? Больше единицы - умножаем. Меньше единицы - делим.
Отрицательные - прибавляем. Если пройти предварительно, то можно понять будет ли четность отрицательных. Если будет четность, то только умножаем и делим
можно поробовать накапливать результат выражения и применяя каждую операцию проверять стало ли накопленное число больше, если меньше, то другая операция и так до конца массива
Владос лучший ! Если не сложно , ответь на вопрос .
Развиваюсь в сфере аналитики и мне интересно знать , как в FAANG обстоят дела с данным направлением , либо может поделишься где можно узнать информацию насчет аналитических направлений в биг тех ?
1. Хранить последное число в переменную last_num
2. Проделать все операции с последним и текущим числом
3. Получить максимальное число из полученных результатов, и хранить в переменную max_num
4. Установить max_num в last_num
P.S: Не учел отрицательные числа)
Но последнее решение даёт максимум и не запоминает порядок мат. действий. Если входной массив пустой, то надо бы вернуть что-то типа undefined
Главное сделать умное табло на превьюшку
Не могу понять, почему с ифами будет дольше, чем второй вариант
Можно же изначально пройти по массиву, посмотреть сколько чисел отрицательных
Затем снова идем по массиву возможны следующие ситуации:
1) Число > 1: умножаем на него
2) число 0 < 1: делим на него
3) число = 1: прибавляем
4) число = 0: прибавляем
5) число -1 < 0: если отрицательных четное количество, то делим, иначе вычитаем
6) число = -1: вычитаем
7) число < -1: если количество отрицательных четное, то умножаем, иначе вычитаем
Неужели 7 ифов будут дольше?
Ты отбросишь варианты, которые могли бы дать больше в перспективе
в первом же примере после числа 1 идет число 2. По вашей логике стоит умножить, но как видим сложение дает лучший результат
@@freedomtv2295нет, у меня же отдельная проверка на 1 - 3 условие
Ифами надо учитывать что у нас в аккумуляторе лежит. Например, [0,2 и 1.5] - здесь лучше сложить, а не умножить.
И быстрее будет вычислить сумму и произведение и их сравнить, чем делать сравнения-вычисления чтобы понять, какую операцию выбрать. Ифы годятся чтобы совсем уж бесперспективные операции не выполнять, вроде деления в примере выше.
Надо не просто минимальное брать, а если это минимальное ОТРИЦАТЕЛЬНОЕ. иначе смысла нет тащить маленькое положительное.
Довольно плохое решение я считаю, но
1)отсортировать массив
2)и проходясь по циклу ставим на все возможные варианты условия(например если меньше единицы и больше -1 прибавляем или отнимаем, а если меньше -1 умножаем или ой чет запутался )
Знаю что очень плохое решение, но это то что пришло в голову в первую очередь
Смотрю дальше!
Если отсортировать массив, то нарушится порядок действий + nlogn уже неоптимально
так там нельзя сортировать
Как насчет этого варианта решения?
double[] nums = {1,-3,0.1,-5};
Arrays.sort(nums);
double max;
for (int i = 1; i < nums.length; i++) {
max = nums[i-1]*nums[i];
double d = nums[i - 1] / nums[i];
double sum = nums[i - 1] + nums[i];
double minus = nums[i - 1] - nums[i];
if(d > max) max=d;
else if(sum > max) max = sum;
else if(minus > max) max = minus;
nums[i] = max;
}
System.out.println(nums[nums.length-1]);
И здесь во втором примере же ответ должен же быть 151? Или по условии задачи последовательность чисел в массиве нельзя менять?
Как решить задачу, если проходиться не последовательно? У меня в голове есть решение и вроде как o(n*n) . Это правильно?
Что-то слишком простая задача, решается сходу. Тянет на изи на литкоде, может медиум-
Если за такое 200к$ платят, то я что-то делаю не так
Влад с интенсива будут видео?
Кажется правильным. Но как доказать, что между min и max нет числа, которое задавало бы новый min или max при +-*/ на любое число.
Понял. Если это умножение на любое число, то оно не рождает новый min или max(деление можно представить в виде умножения: 1 деленное на это число) . Сложение не рождает новый min или max (вычитание можно представить в виде сложения такого же числа с другим знаком)
Дайте ссылку на литкод с этой задачей, кто нибудь
Почему в объяснение ничего не говорится про переполнение. Если тип double то вполне возможно. Если использовать нормальные языки программирования
Какой номер задачи на литкод?
Поставил на паузу. Backtracking?
Для Макс мин не нужно сравнение?, можно использовать готовое?
Интересно где-нибудь на литкоде она есть
time complexity 4^n. Первый пример - 3 елемента в массиве, но операций далеко не 64. Или это не так работает?
по факту 4^(n-1), но константы упускаем, поэтому просто 4^n
Не могу зайти в телегу, при отправке формы сайт кидает ошибку
Разве имеет смысл тащить дальше минимальное значение, если оно не отрицательное?
Если мы потом вычитать будем, то вроде как да
@@Drimondadsесли оно не отрицательное, то вычитать будет точно не нужно
Хорошее замечание! Думаю, что и правда не нужно
Влад Крутоо!!!!!
Мне кажется, что это байка, что задача на 200 000. Она на пятый класс средней школы.
5:47 тут ошибочка, получается 25 а не 36
так сказали, что математический приоритет не играет никакой роли
а что там на мониторе одна и та же шляпа бегает? )))) типо матрица перезагрузка? ))))
а почему рещение Идеальное O(n), если для каждой операции еще нужно минимум и максимум найти
Всегда ищем их среди постоянного числа вариантов, а значит постоянное время на поиск
Эти операции выполняются за константу
Привет! Спасибо за видео. У меня вопрос почему при сложении числа "-3" с числом "1" у тебя получается "4"?
Потому что он взял вычитание сначала 1-(-3), а минус на минус дает +, и как следствие 1+3
А обязательно ли брать всн числа в массиве последовательно. Во втором примере видно, что если нарушить последовательность, можно получить больший результат
Нельзя. В условии задачи операторы можно вставлять только между двумя соседними элементами.
Автор сказал, не меняя последовательность чисел.
спасибо
Почему именно среди программистов столько много каррртавых?
А разве сложность алгоритма не 4**(n-1)?
Константы не учитываются, потому что n может быть бесконечно большим в сравнении с единицей. Поэтому постоянные величины всегда можно опускать для сокращения записи
@@mihusle4187, да, ты прав, спасибо за объяснение)
@@mihusle4187 не всегда, иногда константы решают
O(4^n) эквивалентно по сложности O(4^(n-1))
Да... А я минусы не учел(
🔥
200 баксов за то что ты пообщаешься с якобы гуглуром )) Нууу, без лоха и жизнь плоха
а ти циркач)
If if elif else проснитесь вы обосрались
Отличный ролик, спасибо за труд. (далее будет мой вариант кода)
Писал код до предоставления Владом решения
Написал на python за ~20 минут, если не трудно подскажите как улучшить. Заранее спасибо
from random import randint as r
array = []
while len(array) < 30:
array.append(r(-500, 500)/r(-500, 500))
summ = array[0]
count_of_negative_values = 0
if count_of_negative_values % 2 == 0:
for i in array[1:]:
if i > 0:
summ += max((summ + i), (summ * i), (summ / i))
else:
summ += max(-(summ * i), -(summ / i))
else:
worse_negative_value = float('-0.' + '0' * 100 + '1')
for n in array:
if n < 0:
count_of_negative_values += 1
if max((-10 * n), (-10 / n)) < max((-10 * worse_negative_value), (-10 / worse_negative_value)):
worse_negative_value = n
for i in array[1:]:
if i > 0:
summ += max((summ + i), (summ * i), (summ / i))
elif i != worse_negative_value:
summ += max(-(summ * i), -(summ / i))
else:
summ -= worse_negative_value
print(summ)
Наивный нечукотский юноша, думающий, что организму с видео не наcpaть на комменты под ним 😂
@@TafferDP Я не прошу помощи у автора.
@@timurshamsiev336 Это неважно, он любые комментарии не читает
[-0.9862700228832952, -0.8229166666666666, -1.9513888888888888, 3.8515625, -2.904255319148936] у вас получается (-2.13) а у автора (42.06) итог - не работает