pro.algorithms
Всем привет! Пытаюсь решить задачу https://leetcode.com/problems/longest-increasing-subsequence , но где-то упускаю важную
деталь. Логика ломается на одинаковых последовательностях (7, 7, 7, 7, 7, 7) или [4,10,4,3,8,9]. Не подскажите где ошибка? А то уже глаз замылился.
fun lengthOfLIS(nums: IntArray): Int {
var max = 0
val dp = mutableMapOf<Int, Int>()
for (idx in nums.size - 1 downTo 0) {
val num = nums[idx]
nums
.takeLast(nums.size - idx - 1)
.forEach {
if (num < it)
max = max(max, dp[it]!! + 1)
}
dp[nums[idx]] = max(1, max)
}
return max
}
1 ответов
Aleksandr
Автор вопроса
Кажется ошибка ясна. Проблема в том что именно повторяющиеся элементы и вызывали проблемы, так как брались неверные значения. Тут нет гарантий что значения в массиве уникальные, а у меня мапа используется.
Похожие вопросы
Обсуждают сегодня