LeetCode 300.Longest Increasing Subsequence

preview_player
Показать описание


Thanks in advance!

LeetCode 300. Longest Increasing Subsequence
1. Dynamic Programming
2. Binary Search
  1. happygirlzt
Рекомендации по теме
Longest Increasing Subsequence 0:18:13

Longest Increasing Subsequence - Dynamic Programming - Leetcode 300

LeetCode 300. Longest 0:10:24

LeetCode 300. Longest Increasing Subsequence - O(n log n)

Longest Increasing Subsequence 0:08:32

Longest Increasing Subsequence - Leetcode 300 - Dynamic Programming (Python)

Longest Increasing Subsequence 0:31:05

Longest Increasing Subsequence | Leetcode - 300

Longest increasing subsequence 0:20:44

Longest increasing subsequence

Leetcode 300 Longest 0:05:48

Leetcode 300 Longest Increasing Subsequence

Longest Increasing Subsequence 0:21:00

Longest Increasing Subsequence NlogN | Leetcode #300 | LIS

Longest Increasing Subsequence 0:28:11

Longest Increasing Subsequence (LeetCode 300) | Detailed solution with animations and diagrams

Longest Increasing Subsequence 0:07:09

Longest Increasing Subsequence

LeetCode 300.Longest Increasing 0:10:24

LeetCode 300.Longest Increasing Subsequence

Leetcode - Longest 0:08:01

Leetcode - Longest Increasing Subsequence (Python)

LeetCode 300. Longest 0:12:03

LeetCode 300. Longest Increasing Subsequence [Algorithm + Code Explained ]

Leetcode 300: Longest 0:15:28

Leetcode 300: Longest Increasing Subsequence

300. Longest Increasing 0:20:12

300. Longest Increasing Subsequence - Day 9/31 Leetcode July Challenge

DP 43. Longest 0:16:27

DP 43. Longest Increasing Subsequence | Binary Search | Intuition

Leetcode 300: Longest 0:11:44

Leetcode 300: Longest Increasing Subsequence

Longest Increasing Subsequence 0:16:13

Longest Increasing Subsequence - LeetCode 300 - Python - O(nlog(n))

Longest Increasing Subsequence 0:32:27

Longest Increasing Subsequence | Recursion & Memo |Tree Diagram |DP Concepts & Qns-11 | Leet...

FIND Longest Increasing 0:07:45

FIND Longest Increasing Subsequence - Leetcode 300 #dynamicprogramming

LeetCode 300. Longest 0:10:30

LeetCode 300. Longest Increasing Subsequence | LIS Part 1 | Dynamic Programming

Longest Increasing Subsequence 0:06:27

Longest Increasing Subsequence - LeetCode 300 - JavaScript

300. Longest Increasing 0:24:32

300. Longest Increasing Subsequence | Leetcode Medium

Leetcode 300: Longest 0:56:49

Leetcode 300: Longest Increasing Subsequence

Разбор задачи 300 0:50:27

Разбор задачи 300 leetcode.com Longest Increasing Subsequence. Решение на C++

Комментарии
Автор

Thank you. I couldn't solve the question because I couldn't understand what is meant by subsequence. I thought the example gave the one solution but you pointed out that in fact there are two possible solutions: [2, 5, 7, 101] and [2, 3, 7, 101]. This helped me understand and solve it. Thank you again.

thesuperiorman
Автор

my python conversion with bisect for binary search

class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
import bisect
dp = [0] * len(nums)
length = 0
for num in nums:
idx = bisect.bisect_left(dp, num, 0, length)
dp[idx] = num
if idx == length:
length += 1
return length

aunnfriends
Автор

Thank you for this explanation!
btw Arrays.binarySearch(...) returns the index of the search key, if it is contained in the array within the specified range; otherwise, (-(insertion point) - 1), so I guess in the video it should be "pos = -(index) - 1"

joeybing
Автор

Thanks for the explanation. Question, would the runtime be O(n * log n)? since we do binary search n times and each search takes log(n) and everything else constant?

dnavas
Автор

Very clear explanation. Thank you so much. I cannot express how much you motivate me to continue practicing Leetcode.

domng