- Dynamic programming
- Longest Increasing Subsequence
- Something like Longest Common Subsequence
- In 3, 10, 20, 4, 6, 7, the longest increasing subsequence will be 3, 4, 6, 7
- 1D array can be used unlike Coin change problem
- Multiple subsequences will need to be kept track of here.
- Big O Cheatsheet
- 2^n is bigger and thus worsetime_complexity than n
- n log n is for Sorting algos, is this approach Mergesort or Quicksort?
- Ans. None of above, it is combining a loop and Binary Search
- binary_search will be used thus log n
- The lis array will be sorted.
- We overwrite 10 with 4.
- Similar problem:
- Maximum sum of longest increasing subsequence