def find_minimum_deletions(nums):
# subtracting the length of LIS from the length of the input array to get minimum number of deletions
return len(nums) - find_LIS_length(nums)
def find_LIS_length(nums):
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = 1
maxLength = 1
for i in range(1, n):
dp[i] = 1
for j in range(i):
if nums[i] > nums[j] and dp[i] <= dp[j]:
dp[i] = dp[j] + 1
maxLength = max(maxLength, dp[i])
return maxLength
The solution provided will fail for empty nums as well as the maxLength calculation inside inner for loop can be avoided for optimisation as dp[i] will always increase in the inner loop. So we can directly take it up at the end.
My approach -
def find_minimum_deletions(nums):
lis = 0 #longest_increasing_subsequence
n = len(nums)
dp = [0 for _ in range(n)]
for curr in range(n):
dp[curr] = 1
for prev in range(curr):
if nums[curr] > nums[prev] and dp[curr] <= dp[prev]:
dp[curr] = dp[prev] + 1
lis = max(lis, dp[curr])
return n - lis