Calculate and show here a longest increasing subsequence of the list:
- {3,2,6,4,5,1}
And of the list:
- {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}
Note that a list may have more than one subsequence that is of the maximum length.
#include <iostream> #include <vector> #include <tr1/memory> #include <algorithm> #include <iterator> template <typename E> struct Node { E value; std::tr1::shared_ptr<Node<E> > pointer; }; template <class E> struct node_ptr_less { bool operator()(const std::tr1::shared_ptr<Node<E> > &node1, const std::tr1::shared_ptr<Node<E> > &node2) const { return node1->value < node2->value; } }; template <typename E> std::vector<E> lis(const std::vector<E> &n) { typedef std::tr1::shared_ptr<Node<E> > NodePtr; std::vector<NodePtr> pileTops; // sort into piles for (typename std::vector<E>::const_iterator it = n.begin(); it != n.end(); it++) { NodePtr node(new Node<E>()); node->value = *it; typename std::vector<NodePtr>::iterator j = std::lower_bound(pileTops.begin(), pileTops.end(), node, node_ptr_less<E>()); if (j != pileTops.begin()) node->pointer = *(j-1); if (j != pileTops.end()) *j = node; else pileTops.push_back(node); } // extract LIS from piles std::vector<E> result; for (NodePtr node = pileTops.back(); node != NULL; node = node->pointer) result.push_back(node->value); std::reverse(result.begin(), result.end()); return result; } int main() { int arr1[] = {3,2,6,4,5,1}; std::vector<int> vec1(arr1, arr1 + sizeof(arr1)/sizeof(*arr1)); std::vector<int> result1 = lis(vec1); std::copy(result1.begin(), result1.end(), std::ostream_iterator<int>(std::cout, ", ")); std::cout << std::endl; int arr2[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}; std::vector<int> vec2(arr2, arr2 + sizeof(arr2)/sizeof(*arr2)); std::vector<int> result2 = lis(vec2); std::copy(result2.begin(), result2.end(), std::ostream_iterator<int>(std::cout, ", ")); std::cout << std::endl; return 0; }
- Output:
2, 4, 5, 0, 2, 6, 9, 11, 15,
Content is available under GNU Free Documentation License 1.2.