На протяжении 2 месяцев неспешно решаю задачки на leetcode (нарешал 87 easy, 92 medium, 32 hard, в топ 20% по соревнованиям), параллельно почитываю всякое. Всякие backtracking, BFS, DFS — здорово зашли. Динамическое программирование не идёт, и всё тут. Т.е. я более-менее понимаю как и засчёт чего оно работает, но все задачки, где его можно уместно применить, либо сразу решаю влёт не задумываясь, либо сижу несколько часов — и даже на чужое решение (много чужих решений) смотрю и не понимаю. Часто вижу как решения построены на какой-то очень хитрой логике, которую иначе как хитрожопая сообразительность и не назовёшь. Посоветуйте как поднять уровень — может книжка хорошая есть, может какой-то набор задачек с медленно возрастающим уровнем сложности?

Сейчас вот решал:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

Краткий пересказ.

Даны цены на акции по дням, например prices=[7,1,5,3,6,4]. Можно покупать и продавать 1 акцию. На руках можно держать только 1 акцию. Т.е. если акции нет, её можно купить. Если акция есть, её можно продать. Но если акция есть, вторую купить нельзя. Требуется вычислить наибольший профит, который можно получить если покупать и продавать в правильные дни. В случае предложенного примера ответ будет 7 (покупаем за 1, продаём за 5, покупаем за 3, продаём за 6, выходит: 5-1+6-3=7)

Я сделал полный перебор с мемоизацией — не проходит по времени. Добавил пару if'ов, чтобы некоторые случаи не рассматривать, прошёл по времени — "быстрее, чем 5% всех решений". Молодец, ага.

Стал смотреть чужие решения, товарищ вот тут сделал решение со сложностью O(N). Суть решения в том, чтобы не дёргаться, пока цена падает. На самой низкой цене покупать. Далее не дёргаться пока цена растёт. На самой высокой цене продавать. Интуитивно понятно, что это некий локальный максимум будет. Но совершенно не понятно почему он будет глобальным Что сделать, чтобы мозг на таких вещах не клинило?