Task from JS Interview: The best time to buy stock #1 | Tasks from LeetCode

[@ІльченкоАртем]

Спасибо Вам, Сергей, за эти чудесные и бесценные Ваши видео!

[@frontendscience]

Рад, что было полезно!

[@deniskalinin5101]

очень крутой контент, и подача и визуализация

[@bohdanartemenko]

Эти задачки - прямо то что мне нужно. Очень хорошо прокачивают вообще все)

[@ВоваКоренев-м8ж]

Решил на работе прокачивать своё алгоритмическое мышление, на оценку, но в целом похоже как на видео) const stocks = (arr) => { let total = 0; let minNum = arr[0]; for (let i = 0; i < arr.length; i++) { if (minNum > arr[i]) { minNum = arr[i]; } const newTotal = arr[i] - minNum; if (newTotal > total) { total = newTotal; } } return total; };

[@TanTanyel]

Через reduce, в одну строчку var numbers = [2,4,7,1,9,2]; const maxProfit = (arr) => arr.reduce((a, i) => ({m:(i < a.m ? i : a.m),p:(i-a.m > a.p ? i-a.m : a.p)}),{m:arr[0],p:0}).p; console.log(maxProfit(numbers));

[@frontendscience]

Удивительно компактный но абсолютно не читаемый вариант ))) Благодарю за решение!

[@vadimveksler7645]

Мне на себе 2.5 года назад задали эту задачу ) Живу я в Израиле, так что эта задача актуальна так же и не в России... Похвастаюсь, я смог ее решить давольно быстро... Вакансия была на мидла JS разработчика, с тех пор я работаю в этой компании... ) Помимо этой задачки, было еще несколько на логику и тестовое на дом

[@keiVision]

Больше видосов - больше!!!

[@frontendscience]

Окей-окей)) Утром выйдет! )))

[@AzamatAbduvohidov99]

👍👍

[@lostsouls3151]

Супер!

[@ВладПашковский-ц2э]

Начал пытаться решить через указатели и потерял 2 час. А ответ был так прост :) через цикл, да и вложенность небольшая. Ну век живи век учись. function getMarge(prices) { let maxProfit = 0 let minPrice = prices[0] for (let i = 0; i < prices.length; i++) { if (prices[i] < minPrice) { minPrice = prices[i] } maxProfit = Math.max(maxProfit, prices[i] - minPrice) } return maxProfit }

[@АртемМаслов-к6ъ]

Подскажите, будет ли считаться корректной вот такая запись? let maxProfit = function (prices) { let minPrice = prices[0]; let maxProfit = 0; for (let i = 0; i < prices.length; i++) { minPrice = Math.min(minPrice, prices[i]); maxProfit = Math.max(maxProfit, (prices[i] - minPrice)); } return maxProfit; }

[@ewyslv]

Сергей, спасибо за разбор очередной интересной задачи!)) Случайно обнаружил, что решение не работает при const prices = [6, 8, 4, 3, 1, 2]; Вместо 1 возвращает 2. Фикс ниже в решении: С учетом возможной большой длины массива так будет не оптимальнее? const prices1 = [5, 7, 1, 3, 6, 4]; const prices2 = [6, 8, 4, 3, 1, 2]; const prices3 = [7, 6, 4, 3, 1]; const prices4 = [1]; const prices5 = [5, 7, 1, 3, 6, 8, 4]; const maxProfit = prices => { let min = Math.min(...prices); let max = Math.max(...prices); let minInd = prices.indexOf(min); let maxInd = prices.indexOf(max); if (minInd > maxInd) { const arr = prices.slice(minInd); min = Math.min(...arr); max = Math.max(...arr); } return max - min; }; console.log(maxProfit(prices1)); // 5 console.log(maxProfit(prices2)); // 1 console.log(maxProfit(prices3)); // 0 console.log(maxProfit(prices4)); // 0 console.log(maxProfit(prices5)); // 7

[@UC1C0GDMTjasAdhELHZ6lZNg]

В твоём примере(prices2) если купить в первый день и продать во второй будет выгоднее и ответ действительно 2. А в целом можно твой вариант кода упростить, если находить максимум уже от массива prices.slice(minInd); так как в прошлое уже не вернутся и сделку не совершить. И сразу после этого возвращать max - min Но как в примере с prices2 твоё решение не универсальное.

[@ЕвгенийКутовой-й6ы]

как-то так понятнее показалось... Сергей, а что насчет поиска максимального через Math.max()? мое решение таким образом усложняется до O(n2)? или все так же O(n)? function maxProfit(ar){ let min = ar[0] let minIndex = 0 for(let i=0;i

[@frontendscience]

Да в таком случае сложность выходит таки квадратичная O(n^2).

[@ЕвгенийШут-о7н]

Крутатенюшка

[@frontendscience]

Рад, что угодил! :)

[@hakobandreasyan3955]

👍👍👍👍👍👍 а так ? function maxProfit(arr) { let min = Math.min(...arr) let index = arr.indexOf(min) let max = Math.max(...arr.slice(index + 1)) return Number.isInteger(max - min) ? max - min : 0 }

[@EvilYou]

Решил задачу в лоб сразу, но так и не смог найти более быстрое решение. Если просто искать минимальное число и перебирать массив, то в таком случае вернется 0: [7, 3, 6, 1]. Уже когда Сергей написал min и maxProfit, понял, что к чему. Решение в лоб (сложность O (n^2)) function maxProfit(arr) { let max = 0; for (let i = 0; i < arr.length; i++) { for (let j = i; j < arr.length; j++) { let current = arr[j] - arr[i]; max = Math.max(current, max); } } return max; } Решение тем же способом, что и в видео (сложность O (n)) function maxProfit(arr) { let min = arr[0]; let maxProfit = 0; for (let i = 0; i < arr.length; i++) { min = Math.min(min, arr[i]); let diff = arr[i] - min; if (diff > maxProfit) maxProfit = diff; } return maxProfit; }

[@frontendscience]

отличные варианты решения! Благодарю!

[@EvilYou]

В подобных задачах часто начинают с конца. Мое решение: function maxProfit(arr) { let result = 0; let max = arr[arr.length - 1]; for (let i = arr.length - 2; i >= 0; i--) { if (arr[i] >= max) { max = arr[i]; continue; } result = Math.max(result, max - arr[i]); } return result; } Результат на leetcode: Runtime 61ms Beats 99.84%

[@donybrorahmanov8068]

Всем привет!

[@donybrorahmanov8068]

мой вариант решения через рекурсию let input1 = [7,1,5,3,6,4] //5 let input2 = [7,6,4,3,1] // 0 let input3 = [3,4,5,3,4,1] //2 let input4 = [4,3,7,2,5,1] //4 function findBestSale(daysAndPrice,maxSum=0){ if(daysAndPrice.length === 0){ return console.log(maxSum) } let firstElem = daysAndPrice[0] for (let i=0;i

[@tyomkhachatryan3820]

Опа! let arr = [7,1,5,3,6,4] //5 function maxProfit(arg) { let result let buy = Math.min(...arg) for (let i = 0; i < arg.length; i++) { if(arg[i] === buy){ let res = arg.slice(i, arg.length); result = Math.max(...res) - buy } } return result } console.log(maxProfit(arr))

[@geri_freki]

похоже в цикле лишний шаг у вас - нужна единичка: "for (let i = 0; ..." у меня на питончике вот так: def get_max_profit(prices): min_price, max_profit = prices[0], 0 for current in prices[1:]: min_price = min(current, min_price) max_profit = max(current - min_price, max_profit) return max_profit

[@frontendscience]

Похоже Вы не до конца додумали Вашу мысль. А что будет в случае, если элемента с индексом 1 нету? У меня в коде верно!

[@geri_freki]

@@frontendscience oh my bad )

[@numan0x]

Не знаю JS, написал на питоне. Такой алгоритм: изначально maxProfit=0 1) Ищем топ1 максимальное число 2) Ищем перед ним минимальное число 3) Их разницу сравниваем с maxProfit, большее записываем в maxProfit 4) Ищем топ2 максимальное число 5) Ищем перед ним минимальное число 6) Их разницу сравниваем с maxProfit, большее записываем в maxProfit 7) ... ... ... Так до тех пор, пока очередное (топ макс число минус минимальное во всём массиве) не станет меньше, чем уже текущий maxProfit. Потому что дальше искать нет смысла. Т.е. в наборе [1, 5, 2, 2, 3] после топ1 макс числа 5 - следующее максимальное 3 и 3-1 УЖЕ меньше, чем 4. В итоге это сократит количество итераций. А искать разницу, начиная с максимальных чисел имхо тоже даст сокращение итераций. Так в наборе [1, 4, 6, 3, 9] или [1, 9, 1, 3, 6] первым делом найдётся число 9, затем 1ца перед 9кой, затем их разница 8 и дальше станет ясно что любые остальные переборы бОльшего не дадут. Т.е. в обоих наборах произойдёт 1 итерация вместо множественных. import numpy as np mas = [int(np.random.randint(0,8)) for x in range(6)] print(mas) mas_sorted = mas.copy() mas_sorted = list(set(mas_sorted))[::-1] max_profit = 0 local_min = min(mas_sorted) for i in mas_sorted: if max_profit < i - local_min: b = 1 ind = len(mas) - mas[::-1].index(i) - 1 try: minn = min(mas[:ind]) except: b = 0 if b: razn = i - minn if max_profit < razn: max_profit = razn print('max_profit', max_profit)

[@alexuspro26]

Осталось переписать range(100000000), и посмотреть как оно забуксует. А потом переписать на питоне как в ролике, и удивиться.

[@aleksberg3686]

Не могу понять зачем два массива. Второй я понял 6 дней а первый тогда что обозначает

[@frontendscience]

если вы про input1 и input2 - то это 2 тестовых массива на которых мы проверяем решение.

[@aboba86468]

Кстати решение "в лоб" почему-то не проходит тест с очень большим входным набором данных на leetcode: Time Limit Exceeded. Видимо js слишком медленный для таких неоптимальных решений)

[@EvilYou]

Для массива с 100 000 элементами это 10 миллиардов операций. Вычисления секунд 10 будут занимать на нормальном компе.

[@aboba86468]

@@EvilYou да, но код на Java там предоставлен в качестве одного из способов решения. Его я не запускал, но аналогичный код на js вот ошибку выдаёт.

[@frontendscience]

на литкод специально есть ограничение по времени - чтобы приходилось искать более оптимальные алгоритмы а не "в лоб". То что там есть решение на java в качестве примера способа решения, не значит что оно пройдет тесты.

[@aboba86468]

@@frontendscience Понял, спасибо!

[@iliya8708]

function test(items) { function filter(index) { return function (item, i) { return i > index; } } const result = items.reduce(function (r, c, i, arr) { var f = filter(i); var m = Math.max(...arr.filter(f)); if (r < m - c) { r=m-c; } return r; }, 0); return result; }

[@frontendscience]

Благодарю за решение! К сожалению на больших масивах не проходит теты на LeetCode. Time Limit Exceeded пишет

[@iliya8708]

@@frontendscience спасибо! Учту на будущее

[@ДанилоПідгайний-э2в]

const arr = [7, 1, 5, 4, 3] console.log( arr.map((item, i) => Math.max(...arr.slice(i)) - item) .reduce((a, b) => Math.max(a, b), 0) ); Трішки поїхало. Спочатку отримаємо профіт для кожного числа в масіві, потім найбільший профіт більше за 0

[@evgeniichikishev2096]

почему так нельзя сделать? function profit(arr) { const min = Math.min(...arr); const indexMin = arr.indexOf(min); const max = Math.max(...(arr.slice(indexMin))); const indexMax = arr.lastIndexOf(max); return arr[indexMax] - arr[indexMin]; }

[@старыйшэд]

как так maxProfit = 5, купил же за 1 продал за 5, профит 4

[@frontendscience]

купил за 1 а продал за 6 в 5й день - профит = 5

[@frontendscience]

посмотрите еще раз: 1:18

[@старыйшэд]

@@frontendscience да точно

[@Декопитатор321]

а у меня так получилось) убогое конечно решение, но мне главное что у меня получилось)) function maxProfit(prices) { let mas = [] var min = Math.min.apply(null, prices); let count = prices.indexOf(min) for(let i = 0; i < prices.length; i++){ if(prices.indexOf(prices[i]) > count){ mas.push(prices[i]) } } var max = Math.max.apply(null, mas) if(max === -Infinity){ return 0 } return max }

[@whiteguards43]

А почему нельзя сделать так? Найти максимальный элемент в массиве, Math.min() нйти его индекс, и с этим индексом сделать сплай скинуть левую часть, и в оставшемся массиве сделать Math.max и отнять результат, если в оставшемся массиве макс и мин равны, то вернуть 0

[@ovocado9965]

var maxProfit = function(prices) { let maxProfit = 0; let minPrice = prices[0]; prices.forEach(currPrice => { minPrice = Math.min(minPrice, currPrice); maxProfit = Math.max(maxProfit, currPrice - minPrice); }) return maxProfit };

[@GreenGotty]

Вот так вышло. Не скоростью, так памятью! :) Runtime: 148 ms, faster than 27.16 % of JavaScript online submissions for Best Time to Buy and Sell Stock. Memory Usage: 48.1 MB, less than 98.57 % of JavaScript online submissions for Best Time to Buy and Sell Stock. var maxProfit = function (prices) { var min = prices[0], profit = 0; for (let i = 1; i < prices.length; i++) { const marg = prices[i] - min; if (marg < 0) { min = prices[i]; continue; } if (marg > profit) { profit = marg; } } return profit; };

[@frontendscience]

Благодарю за решение! Отличный вариант!

[@marksobolev9059]

function maxProfit2(arr) { let min = arr[0]; let maxProfit = 0; for (let i = 0; i < arr.length; i++) { min = Math.min(min, arr[i]); maxProfit = Math.max(maxProfit, arr[i] - min) } return maxProfit; } как то так

[@МаксимЛибер-ф2н]

У меня вот так получилось: const maxProfit = function(prices) { const min = Math.min(...prices) const max = Math.max(...(prices.slice(prices.indexOf(min)))) return max - min }; Как Вам?

[@happyuaman]

У тебя оно не будет работать если самое маленькое число стоит в конце массива, к примеру вот такой массив const go = [8, 2, 6, 2, 1]; , там можно получить профит в 4 монетки, но твоя функция выдаст 0.

[@frontendscience]

Там уже тебе ответили - к сожалению такой вариант не сработает. надо искать именно самую глубокую впадину и следующий за ней максимальный пик. если минимальное значение будет в самом конце - то мы не можем после него сделать покупку.

[@nurtumal4655]

Вот мое решение на Java, получилось хуже, потратил O(n) памяти и итераций больше, хотя в идеале можно было обойтись и двумя переменными и одним циклом. public int maxProfit(int[] prices) { SortedMap map = new TreeMap(); for (int num : prices) map.merge(num, 1, Integer::sum); int res = 0; for (int num : prices) { map.merge(num, -1, Integer::sum); if (map.get(num) == 0) map.remove(num); if (map.size() > 0) res = Math.max(map.lastKey() - num, res); } return res; }

[@frontendscience]

Благодарю за решение!

[@ПавелФ-з3ш]

Ни одной не решил 😢

[@imbydlo1552]

Ничего не понял но очень интересно

[@lansserrat8861]

Да чего тут непонятного, здесь тыкнул, там нажал, там что-то покликал - и готово!

[@krkaa8663]

function maxProfit(prices) { let largest = 0; let lowPrice = Number.MAX_VALUE; for (let i = 0; i < prices.length; i++) { if (prices[i] < lowPrice) { lowPrice = prices[i]; } else if (prices[i] - lowPrice > largest) { largest = prices[i] - lowPrice }; } return largest; }

[@frontendscience]

Отличный вариант!

[@ghost8652]

Предлагаю свой вариант решения: const maxProfit = prices => { let maxProfit = 0; let current = 0; while (current < prices.length - 1) { if (prices[current + 1] - prices[current] > maxProfit) { maxProfit = prices[current + 1] - prices[current]; }; current++; } return maxProfit; };

[@carved1883]

function maxProfit(array){ let maxPrice; let minPrice; let arrTwo = []; for(let i = 0; i < array.length; i++){ if(array[i] === Math.min(...array)){ minPrice = array[i] let minIndex = array.indexOf(array[i]) arrTwo = array.splice(minIndex) maxPrice = Math.max(...arrTwo) } } console.log(maxPrice - minPrice) }