LIS.H File Reference

Longest Increasing Subsequence (LIS) via patience sorting. More...

#include <algorithm>
#include <cstddef>
#include <limits>
#include <utility>
#include <ahFunction.H>
#include <tpl_array.H>

Include dependency graph for LIS.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::LIS_Result< T >
	Result of a LIS computation. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::lis_detail

Functions
template<typename T , class Compare >
size_t	Aleph::lis_detail::lower_bound_pos (const Array< T > &tails, const T &value, Compare cmp)
template<typename T , class Compare >
size_t	Aleph::lis_detail::upper_bound_pos (const Array< T > &tails, const T &value, Compare cmp)
template<typename T , class Compare = Aleph::less<T>>
LIS_Result< T >	Aleph::longest_increasing_subsequence (const Array< T > &seq, Compare cmp=Compare())
	Compute the Longest Increasing Subsequence (patience sorting).
template<typename T , class Compare = Aleph::less<T>>
size_t	Aleph::lis_length (const Array< T > &seq, Compare cmp=Compare())
	Compute only the length of the LIS (no reconstruction).
template<typename T , class Compare = Aleph::less<T>>
LIS_Result< T >	Aleph::longest_nondecreasing_subsequence (const Array< T > &seq, Compare cmp=Compare())
	Compute the Longest Non-Decreasing Subsequence.

Detailed Description

Longest Increasing Subsequence (LIS) via patience sorting.

Provides O(n log n) computation of the longest increasing subsequence using patience sorting with binary search, plus optional reconstruction of the actual subsequence.

Definition in file LIS.H.