Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3] Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7] Output: 1
Constraints:
1 <= nums.length <= 2500-10^4 <= nums[i] <= 10^4
Follow up:
O(n^2) solution?O(n log(n)) time complexity?
The description was taken from https://leetcode.com/problems/longest-increasing-subsequence/.
#O(N^2) Time, O(N) Spaceclass Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(0, i): if nums[i] > nums[j]: dp[i] = max(dp[i], 1 + dp[j]) return max(dp)If we are looking for a specific subsequence, not a sublist, that follows a specific constraint, that is typically an indication that Dynamic Programming can be applied.
That is how we will solve this problem.
More specifically, we can build an array that we will use as a lookup table. We will split the input array into subproblems of length one, two, three, etc. Within each subproblem, we will be asking "can we extend the length of an increasing subsequence up to this index?", if the answer is yes then we will increase the subsequence by the current index and repeat.
We can then increase the maximum value in our lookup table, which would be the longest streak of "yes" we were able to answer from each subproblem question.
If the input array is empty then the longest increasing subsequence would be zero.
if not nums: return 0
We will create our dp array where each index will hold the longest increasing subsequence up until that point. The base case will be the value of one for each index because at minimum each value will be a subsequence of one, the element itself.
dp = [1] * len(nums)
We will then create our "expansion" loop, with the iterator i and this loop will traverse to the last index of the input array. This is the loop that we will use to expand the range of our subproblem.
for i in range(1, len(nums)):
Next, we will create our "subproblem partition" loop with the iterator j and this loop will only focus on the subproblem partition between the first index of the input array up to the index i is at.
for j in range(0, i):
We will compare the elements at i and j.
If the element in the input array at i is less than or equal to the element at j then we don't have an increasing subsequence between the two elements, so we will just continue.
If that is not the case, we have an increasing subsequence at least between these two elements so we will ask our subproblem question, "should the index at i stay in the subsequence it is already in, or should it hop into the subsequence j is in, which would be the greatest number so far?".
if nums[i] > nums[j]: dp[i] = max(dp[i], 1 + dp[j])
The reason we don't automatically add i to the subsequence is because i could already be in a subsequence with a greater length, so we wouldn't want to ruin its high score in the dp table by writing a lower length score.
Once we are done with filling our dp array with each score of the longest increasing subsequence lengths, we will return what the highest score is.
return max(dp)
By the time we are done with building the dp table, it will look like the bottom row of this table shown below, with the top row being the input array.
| 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 |
Notice we can use our eyes to scan the first row from left to right while counting out loud the length of each increasing subsequence and each count we say will be written in the box below it.