Skip to main content
Computer Science

Return to Answer

added 2 characters in body
Source Link
user6530
user6530
  • 954
  • 1
  • 5
  • 17

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n$$x+y\leq n+1$, see here. Notice that the reference gives a constructive proof.

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n$, see here. Notice that the reference gives a constructive proof.

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n+1$, see here. Notice that the reference gives a constructive proof.

added 54 characters in body
Source Link
user6530
user6530
  • 954
  • 1
  • 5
  • 17

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n$, see here. Notice that the reference gives a constructive proof.

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n$, see here.

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n$, see here. Notice that the reference gives a constructive proof.

Source Link
user6530
user6530
  • 954
  • 1
  • 5
  • 17

There are also short sequences that satisfy your request. Consider for example the first 16 terms of the binary Van der Corput sequence $$ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15. $$ In general there exists a sequence $T$ of length $n\geq1$ containing a longest increasing subsequence of length $x\geq 1$ and a longest decreasing subsequence of length $y\geq 1$ if and only if the numbers $x$, $y$ and $n$ satisfy the conditions $x\cdot y\geq n$ and $x+y\leq n$, see here.