Rosetta Code

Longest increasing subsequence: Difference between revisions

Page Discussion

Longest increasing subsequence (view source)

Revision as of 20:15, 21 October 2021

33 bytes removed ,  2 years ago
→‎{{header|C++}}
(→‎Python: Patience sorting method: use python slice technique (x[i:i+k] = [...]) to simplify if-else case for replace/append new node)
Line 422:
=={{header|C++}}==
Patience sorting
<lang cpp>#include <iostreamvector>
#include <vectorlist>
#include <tr1/memory>
#include <algorithm>
#include <iteratoriostream>
 
template <typename ET>
struct Node {
E T value;
Node* prev_node;
std::tr1::shared_ptr<Node<E> > pointer;
};
 
template <classtypename EContainer>
Container lis(const Container& values) {
struct node_ptr_less {
using E = typename Container::value_type;
bool operator()(const std::tr1::shared_ptr<Node<E> > &node1,
using NodePtr node(new= Node<E>())*;▼
const std::tr1::shared_ptr<Node<E> > &node2) const {
using ConstNodePtr = const NodePtr;
return node1->value < node2->value;
}▼
};▼
 
std::vector<NodePtr> pileTops;▼
std::vector<Node<E>> nodes(values.size());
 
// sort into piles▼
template <typename E>▼
auto cur_node = std::begin(nodes);
std::vector<E> lis(const std::vector<E> &n) {
for (auto cur_value = std::begin(values); cur_value != std::end(values); ++cur_value, ++cur_node)
typedef std::tr1::shared_ptr<Node<E> > NodePtr;
{
auto node = &*cur_node;
node->value = *itcur_value;▼
 
// lower_bound returns the first element that is not less than 'node->value'
▲ std::vector<NodePtr> pileTops;
auto lb = std::lower_bound(pileTops.begin(), pileTops.end(), node, node_ptr_less<E>());▼
▲ // sort into piles
[](ConstNodePtr& node1, ConstNodePtr& node2) -> bool { return node1->value < node2->value; });
for (typename std::vector<E>::const_iterator it = n.begin(); it != n.end(); it++) {
 
▲ NodePtr node(new Node<E>());
if (lb != pileTops.begin())
▲ node->value = *it;
node->prev_node = *std::prev(lb);
typename std::vector<NodePtr>::iterator j =
 
▲ std::lower_bound(pileTops.begin(), pileTops.end(), node, node_ptr_less<E>());
if (jlb !== pileTops.beginend())
node->pointer = * pileTops.push_back(j-1node);
if (j != pileTops.end()) else
*jlb = node;
else}
 
pileTops.push_back(node);
// extract LIS from piles
}
// extractnote that LIS fromlength is equal to the number of piles
std::vector<E> Container result(pileTops.size());
auto r = std::rbegin(result);
for (NodePtr node = pileTops.back(); node != NULL; node = node->pointer)▼
 
result.push_back(node->value);▼
▲ for (NodePtr node = pileTops.back(); node != NULLnullptr; node = node->pointerprev_node, ++r)
std::reverse(result.begin(), result.end());
▲ result.push_back( *r = node->value);
return result;▼
 
▲ return result;
}
 
▲template <typename EContainer>
int main() {▼
void show_lis(const Container& values)
int arr1[] = {3,2,6,4,5,1};
{
std::vector<int> vec1(arr1, arr1 + sizeof(arr1)/sizeof(*arr1));
std::vector<int> result1 auto&& result = lis(vec1values);
for (auto& r : result) {
std::copy(result1.begin(), result1.end(), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endlr << ' ';
▲ }
std::cout << std::endl;▼
▲};
 
▲int main() {
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));
show_lis(std::vectorlist<int> result2{ =3, lis(vec22, 6, 4, 5, 1 });
▲ int arr2[] =show_lis(std::vector<int> { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 });
std::copy(result2.begin(), result2.end(), std::ostream_iterator<int>(std::cout, ", "));
▲ std::cout << std::endl;
return 0;
}</lang>
 
{{out}}
<pre>2, 4, 5,
0, 2, 6, 9, 11, 15, </pre>
 
=={{header|Clojure}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/234596"