Given an integer array nums
, return the length of the longest strictly increasing subsequence.
For example:
nums = [10,9,2,5,3,7,101,18]
The longest increasing subsequence is [2,3,7,101]
, therefore the length is 4.
nums = [0,1,0,3,2,3]
The longest increasing subsequence is [0, 1, 2, 3]
, therefore the length is 4.
nums = [7,7,7,7,7,7,7]
The longest increasing subsequence is [7]
, therefore the length is 1.
What is the most efficient way to solve this problem?
Given an integer array nums
, find the length of the longest strictly increasing subsequence.
A brute-force approach would involve generating all possible subsequences of the input array and then checking each subsequence to see if it is strictly increasing. We would then keep track of the longest increasing subsequence found so far.
Complexity:
We can solve this problem more efficiently using dynamic programming. Let dp[i]
be the length of the longest increasing subsequence ending at index i
.
dp[i]
to 1 for all i
, because the minimum length of an increasing subsequence ending at i
is 1 (the element itself).nums
from left to right. For each element nums[i]
, iterate through all the elements before it (nums[j]
where j < i
).
nums[i] > nums[j]
, it means we can extend the longest increasing subsequence ending at j
by including nums[i]
. So, we update dp[i]
to max(dp[i], dp[j] + 1)
. This step means that we check if adding the current element would give us a longer increasing subsequence than what we currently have.dp
array will be the length of the longest increasing subsequence.Complexity:
dp
array.Edge Cases:
def lengthOfLIS(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # Initialize dp array with 1
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Follow-up: O(n log n) Solution:
It is possible to improve the time complexity to O(n log n) using a combination of binary search and dynamic programming. This approach involves maintaining a "tails" array, where tails[i]
is the smallest tail of all increasing subsequences of length i+1
. Then we iterate through the input nums
array and update tails
. For each number num
in nums
we can do one of the following: If num
is larger than all tails, then we extend the largest subsequence by adding num
. If num
is not larger than all tails, then we find the smallest tail that is >= num
and replace with num
. By doing this, we maintain the property that tails
array is always sorted in increasing order.
Complexity:
tails
array.import bisect
def lengthOfLIS_optimized(nums):
tails = []
for num in nums:
i = bisect.bisect_left(tails, num)
if i == len(tails):
tails.append(num)
else:
tails[i] = num
return len(tails)