84 lines
2.4 KiB
C++
84 lines
2.4 KiB
C++
#include <vector>
|
|
#include <list>
|
|
#include <algorithm>
|
|
#include <iostream>
|
|
|
|
template <typename T>
|
|
struct Node {
|
|
T value;
|
|
Node* prev_node;
|
|
};
|
|
|
|
template <typename T>
|
|
bool compare (const T& node1, const T& node2)
|
|
{
|
|
return node1->value < node2->value;
|
|
}
|
|
|
|
template <typename Container>
|
|
Container lis(const Container& values) {
|
|
typedef typename Container::value_type E;
|
|
typedef typename Container::const_iterator ValueConstIter;
|
|
typedef typename Container::iterator ValueIter;
|
|
typedef Node<E>* NodePtr;
|
|
typedef const NodePtr ConstNodePtr;
|
|
typedef std::vector<Node<E> > NodeVector;
|
|
typedef std::vector<NodePtr> NodePtrVector;
|
|
typedef typename NodeVector::iterator NodeVectorIter;
|
|
typedef typename NodePtrVector::iterator NodePtrVectorIter;
|
|
|
|
std::vector<NodePtr> pileTops;
|
|
std::vector<Node<E> > nodes(values.size());
|
|
|
|
// sort into piles
|
|
NodeVectorIter cur_node = nodes.begin();
|
|
for (ValueConstIter cur_value = values.begin(); cur_value != values.end(); ++cur_value, ++cur_node)
|
|
{
|
|
NodePtr node = &*cur_node;
|
|
node->value = *cur_value;
|
|
|
|
// lower_bound returns the first element that is not less than 'node->value'
|
|
NodePtrVectorIter lb = std::lower_bound(pileTops.begin(), pileTops.end(), node, compare<NodePtr>);
|
|
|
|
if (lb != pileTops.begin())
|
|
node->prev_node = *(lb - 1);
|
|
|
|
if (lb == pileTops.end())
|
|
pileTops.push_back(node);
|
|
else
|
|
*lb = node;
|
|
}
|
|
|
|
// extract LIS from piles
|
|
// note that LIS length is equal to the number of piles
|
|
Container result(pileTops.size());
|
|
std::reverse_iterator<ValueIter> r = std::reverse_iterator<ValueIter>(result.rbegin());
|
|
|
|
for (NodePtr node = pileTops.back(); node; node = node->prev_node, ++r)
|
|
*r = node->value;
|
|
|
|
return result;
|
|
}
|
|
|
|
template <typename Container>
|
|
void show_lis(const Container& values)
|
|
{
|
|
const Container& result = lis(values);
|
|
for (typename Container::const_iterator it = result.begin(); it != result.end(); ++it) {
|
|
std::cout << *it << ' ';
|
|
}
|
|
std::cout << std::endl;
|
|
}
|
|
|
|
int main()
|
|
{
|
|
const int arr1[] = { 3, 2, 6, 4, 5, 1 };
|
|
const int arr2[] = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
|
|
|
|
std::vector<int> vec1(arr1, arr1 + sizeof(arr1) / sizeof(arr1[0]));
|
|
std::vector<int> vec2(arr2, arr2 + sizeof(arr2) / sizeof(arr2[0]));
|
|
|
|
show_lis(vec1);
|
|
show_lis(vec2);
|
|
}
|