LIS.H File Reference

Longest Increasing Subsequence (LIS) algorithms. 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 Longest Increasing Subsequence 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 (strictly increasing).
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) algorithms.

The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.

This header provides high-performance O(n log n) solutions using the Patience Sorting algorithm with binary search.

Variants Provided

• LIS: Strictly increasing subsequence (a < b < c).
• Longest Non-Decreasing Subsequence: (a <= b <= c).
• Length-only: space-optimized O(n) space version.

Complexity

Algorithm	Time	Space
LIS (with reconstruction)	O(n log n)	O(n)
LIS (length only)	O(n log n)	O(n)

Example

Array<int> seq = {10, 22, 9, 33, 21, 50, 41, 60, 80};
 
// 1. Compute strictly increasing LIS
auto res = longest_increasing_subsequence(seq);
// res.length = 6
// res.subsequence = {10, 22, 33, 50, 60, 80}
 
// 2. Compute non-decreasing LIS
Array<int> seq2 = {1, 2, 2, 3, 1};
auto res2 = longest_nondecreasing_subsequence(seq2);
// res2.length = 4
// res2.subsequence = {1, 2, 2, 3}
 
// 3. Length only (faster, less memory)
size_t len = lis_length(seq); // returns 6

Definition in file LIS.H.