I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.
相关问题
- Finding k smallest elements in a min heap - worst-
- binary search tree path list
- High cost encryption but less cost decryption
- How to get a fixed number of evenly spaced points
- Space complexity of validation of a binary search
相关文章
- What are the problems associated to Best First Sea
- Coin change DP solution to keep track of coins
- Algorithm for partially filling a polygonal mesh
- Robust polygon normal calculation
- Algorithm for maximizing coverage of rectangular a
- How to measure complexity of a string?
- Select unique/deduplication in SSE/AVX
- How to smooth the blocks of a 3D voxel world?
O(n^2) java implementation:
This can be solved in O(n^2) using Dynamic Programming. Python code for the same would be like:-
For input:
5 19 5 81 50 28 29 1 83 23
output would be:
[1, 2, 1, 3, 3, 3, 4, 1, 5, 3] 5
The list_index of output list is the list_index of input list. The value at a given list_index in output list denotes the Longest increasing subsequence length for that list_index.
Here is a Scala implementation of the O(n^2) algorithm:
This is a Java implementation in O(n^2). I just did not use Binary Search to find the smallest element in S, which is >= than X. I just used a for loop. Using Binary Search would make the complexity at O(n logn)
here is java O(nlogn) implementation
Petar Minchev's explanation helped clear things up for me, but it was hard for me to parse what everything was, so I made a Python implementation with overly-descriptive variable names and lots of comments. I did a naive recursive solution, the O(n^2) solution, and the O(n log n) solution.
I hope it helps clear up the algorithms!
The Recursive Solution
The O(n^2) Dynamic Programming Solution
The O(n log n) Dynamic Programming Solution