Dynamic Programming II#
This section focuses on longest increasing subsequence problems.
Leetcode
0300
0673
0646
1218
1027
0354
1964
1. Longest Increasing Subsequence#
Dynamic Programming#
Binary Search#
Patience sort can be used here to find the longest increaseing subsequence in \(O(Nlog(N))\) time.
2. Number of Longest Increasing Subsequence#
3. Longest Arithmetic Subsequence of Given Difference#
4. Longest Arithmetic Subsequence#
Leetcode 1027
We can use a dicitionary to represent the states for the dp table when negative index is present.