File SequenceProblems.h

↰ Parent directory (ADS/optimization)

Problems of optimization on a sequence, solved by a scan or by the dynamic programming of the longest increasing subsequence [see File Subsequences.h]:

Definition (ADS/optimization/SequenceProblems.h)

Detailed Description

  • trappingRainWater(): the water held by columns of heights h_i after the rain, :math:` sum_i min( max_{j leq i} h_j , max_{j geq i} h_j ) - h_i ; two indices from the ends, the lower side moving inwards, since its level is fixed by its own maximum: :math: Theta( n ) ` time and O( 1 ) space, instead of the two arrays of the maxima or the stack of the decreasing columns.

  • largestDivisibleSubset(): the largest subset of distinct positive integers in which of any two one divides the other: on the items sorted, a chain in the order of divisibility, :math:` L[ i ] = 1 + max{ L[ j ] : j < i , a_j mid a_i } , right by the transitivity of divisibility; :math: Theta( n^2 ) ` time.

  • maxSumIncreasingSubsequence(): the largest sum of a strictly increasing subsequence, the heaviest increasing subsequence with the items as weights: :math:` D[ i ] = a_i + max{ D[ j ] : j < i , a_j < a_i } , the maximum over the smaller values from a Fenwick tree of the prefix maxima on the ranks, :math: O( n log n ) ` time instead of the :math:` Theta( n^2 ) ` scan.

  • longestChainSubsequence(): the longest subsequence of S each item of which precedes the next in a strict partial order, e.g. boxes each fitting in the next, :math:` L[ j ] = 1 + max{ L[ i ] : i < j , S_i prec S_j } , :math: Theta( n^2 ) ` comparisons; for a total order it is the longest increasing subsequence, in O( n log n ). In d dimensions, the boxes free to be sorted and rotated give the box stacking problem, the longest path in the DAG of the dominance.

  • longestDistinctSegment(): the longest segment of A with no value repeated, by a window whose left end jumps past the last occurrence of a repeated value, with a hash table of the last occurrences; :math:` Theta( n ) ` expected time.

The contracts [see File Contract.h]: the items of largestDivisibleSubset() positive and distinct, and the subset divisible; the subsequences found increasing in the given order. The functions are defined in SequenceProblems.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

  1. Jacobson, K.-P. Vo, Heaviest increasing/common subsequence problems, Proc. 3rd Symposium on Combinatorial Pattern Matching, LNCS 644, 52-66, 1992, doi:10.1007/3-540-56024-6_5

    1. Fenwick, A new data structure for cumulative frequency tables, Software: Practice and Experience 24(3), 327-336, 1994, doi:10.1002/spe.4380240306

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

  • ADS/Contract.h (File Contract.h)

  • ADS/optimization/impl/SequenceProblems.tpp

  • algorithm (File AkraBazzi.h)

  • concepts

  • cstddef

  • functional

  • unordered_map

  • utility

  • vector

Namespaces

Functions