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 = 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