Longest increasing subsequence
Context
I first decided to solve it using greedy means keep taking larger numbers.
What broke
Tried this code current = nums[0] length = 1 for num in nums: if num > current: length += 1 current = num but if the given numbers are 1,8,2,3,4 then it picks 1->8 and given length=2 but the actual answer is 1,2,3,4 length=4
Reasoning
after failed attempt using greedy i decided to use DP because here local optimal is not giving global optimal answer. after some more failed attempts realized binary search + DP is the best possible solution for it o(nlogn)
The Fix / Solution
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)