longest_increasing_subsequence
1# @leet start 2class Solution: 3 def lengthOfLIS(self, nums: list[int]) -> int: 4 """ 5 For this problem we're tasked with returning the length of the longest increasing 6 subsequence. For 7 [10, 9, 2, 5, 3, 7, 101, 18], that would be [2, 3, 7, 101] 8 9 If we do this naively, this can be done with DFS in (2^n) time, because 10 for every number, we want to find the numbers that are larger than it 11 recursively, which requires n * n computations for n items. 12 13 To make this faster, we have to solve subproblems for each number. 14 15 For each number, we know the value of the numbers previous to it. 16 We also can store the longest increasing subsequence up to that point 17 in an extra array. Thus, we can solve this problem by building up 18 the longest increasing subsequence by iterating through the array 19 and for every item, building up a recurrence relation, where $v_i$ is 20 the max of all the items that came before it + 1 if it is smaller 21 than the number, otherwise, just the number itself. 22 23 We can do this for all the items in the given array and return the max 24 of our answers, which answers the question. 25 """ 26 n = len(nums) 27 dp = [1 for _ in range(n)] 28 29 for i in range(1, n): 30 for j in range(i): 31 if nums[i] > nums[j]: 32 dp[i] = max(dp[i], dp[j] + 1) 33 34 return max(dp) 35 36 37# @leet end 38 39 40def test(): 41 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def lengthOfLIS(self, nums: list[int]) -> int: 5 """ 6 For this problem we're tasked with returning the length of the longest increasing 7 subsequence. For 8 [10, 9, 2, 5, 3, 7, 101, 18], that would be [2, 3, 7, 101] 9 10 If we do this naively, this can be done with DFS in (2^n) time, because 11 for every number, we want to find the numbers that are larger than it 12 recursively, which requires n * n computations for n items. 13 14 To make this faster, we have to solve subproblems for each number. 15 16 For each number, we know the value of the numbers previous to it. 17 We also can store the longest increasing subsequence up to that point 18 in an extra array. Thus, we can solve this problem by building up 19 the longest increasing subsequence by iterating through the array 20 and for every item, building up a recurrence relation, where $v_i$ is 21 the max of all the items that came before it + 1 if it is smaller 22 than the number, otherwise, just the number itself. 23 24 We can do this for all the items in the given array and return the max 25 of our answers, which answers the question. 26 """ 27 n = len(nums) 28 dp = [1 for _ in range(n)] 29 30 for i in range(1, n): 31 for j in range(i): 32 if nums[i] > nums[j]: 33 dp[i] = max(dp[i], dp[j] + 1) 34 35 return max(dp)
def
lengthOfLIS(self, nums: list[int]) -> int:
4 def lengthOfLIS(self, nums: list[int]) -> int: 5 """ 6 For this problem we're tasked with returning the length of the longest increasing 7 subsequence. For 8 [10, 9, 2, 5, 3, 7, 101, 18], that would be [2, 3, 7, 101] 9 10 If we do this naively, this can be done with DFS in (2^n) time, because 11 for every number, we want to find the numbers that are larger than it 12 recursively, which requires n * n computations for n items. 13 14 To make this faster, we have to solve subproblems for each number. 15 16 For each number, we know the value of the numbers previous to it. 17 We also can store the longest increasing subsequence up to that point 18 in an extra array. Thus, we can solve this problem by building up 19 the longest increasing subsequence by iterating through the array 20 and for every item, building up a recurrence relation, where $v_i$ is 21 the max of all the items that came before it + 1 if it is smaller 22 than the number, otherwise, just the number itself. 23 24 We can do this for all the items in the given array and return the max 25 of our answers, which answers the question. 26 """ 27 n = len(nums) 28 dp = [1 for _ in range(n)] 29 30 for i in range(1, n): 31 for j in range(i): 32 if nums[i] > nums[j]: 33 dp[i] = max(dp[i], dp[j] + 1) 34 35 return max(dp)
For this problem we're tasked with returning the length of the longest increasing subsequence. For [10, 9, 2, 5, 3, 7, 101, 18], that would be [2, 3, 7, 101]
If we do this naively, this can be done with DFS in (2^n) time, because for every number, we want to find the numbers that are larger than it recursively, which requires n * n computations for n items.
To make this faster, we have to solve subproblems for each number.
For each number, we know the value of the numbers previous to it. We also can store the longest increasing subsequence up to that point in an extra array. Thus, we can solve this problem by building up the longest increasing subsequence by iterating through the array and for every item, building up a recurrence relation, where $v_i$ is the max of all the items that came before it + 1 if it is smaller than the number, otherwise, just the number itself.
We can do this for all the items in the given array and return the max of our answers, which answers the question.
def
test():