## 5.237. longest_increasing_sequence

Origin

constraint on sequences

Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi »},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Synonym

$\mathrm{\pi \pi \pi £\pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$.

Arguments
 $\mathrm{\pi »}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$
Restrictions
 $\mathrm{\pi »}\beta ₯0$ $\mathrm{\pi »}<$$\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

$\mathrm{\pi »}$ is the largest difference between the first and the last value of the maximum increasing sequences of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

A sequence of consecutive variables ${X}_{i},{X}_{i+1},\beta ―,{X}_{j}$ ($1\beta €i\beta €j\beta €|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$) of the collection of variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ is a maximum increasing sequence if all the following conditions simultaneously apply:

• ${X}_{i}\beta €{X}_{i+1}\beta €\beta ―\beta €{X}_{j}$,

• $i=1$ or ${X}_{i-1}>{X}_{i}$,

• $i=|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ or ${X}_{j}>{X}_{j+1}$.

Example
 $\left(7,β©10,8,8,6,4,9,11,8βͺ\right)$ $\left(0,β©10,8,7,5,4,3,1,0βͺ\right)$

FigureΒ 5.237.1 gives a graphical representation of the first example of the Example slot with its two maximum increasing sequences in red of respective size 0 and 7. The corresponding $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint holds since its first argument $\mathrm{\pi »}$ is fixed to the maximum size 7.

Typical
 $\mathrm{\pi »}>0$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>2$
Symmetry

One and the same constant can be added to the $\mathrm{\pi \pi \pi }$ attribute of all items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Arg. properties

Functional dependency: $\mathrm{\pi »}$ determined by $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$: domains $0..n$

Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

062070252924343212870
1218122750441225382144314
211616113981136189132685090
3-101621942208162111062074365
4--1102024289303750844603682
5---1410301345067667792840
6----2107252264810197174
7-----36360210379696
8------7156690

Solution count for $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$: domains $0..n$

FigureΒ 5.237.2 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ constraint.