Question
Given an integer array
nums, return the length of the longest strictly increasing .
Idea
- Sort of like solving Leetcode - House Robber
- Recursion
- Choices
- Take the current index
- Skip the current index
- If our i goes out of index, we want to return 0 since we can’t add any more items to the subsequence
- We need to keep track of our current index and the index of the previous “largest” array item
- If we skip the current index, we keep our previous largest number
- We can only include another element if it is larger than our previous largest number
- If this is the case, we need to update our largest number
- We can make this more efficient by applying Memoization
- Here, we want to store the result of each index in the form ([result, j]) (starting from the last index which is our base case) up to 0 which will store our result
- Bottom up DP
- At the very last index of our array, we know that our res is 1, since the longest subsequence we can make is of length 1
- At the n-1 position, we know at most, we can be 1+dp[i+1]=2
- At the n-2 position, we know at most, we can be 1+dp[i+1]=3 but we could also be 2 (including the n-2 position and the n position without the n-1 position so we need to check the entire remainder of the array)
- We can only accept an addition to the subsequence if nums[i] < nums[j], where j is the subsequent array position we are checking, we want to update our tabulated result if there is a larger subsequence later on in the array
- Top down DP
- Uses Memoization, so this is our recursive solution
- A similar structure to our bottom up approach, where we still need to check for all i’s and j’s except we use recursion to propagate our result up