Skip to main content
Computer Science

Return to Question

More descriptive title
Source Link
John L.
John L.
  • 39.1k
  • 4
  • 34
  • 91

Proof of existence Existence / non-existence of such a sequence with short longest increasing subsequence and decreasing subsequence?

Proof of existence Existence / non-existence of such a sequence with short longest increasing subsequence and decreasing subsequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

Proof of existence / non-existence of such a sequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

Became Hot Network Question
added 114 characters in body; added 2 characters in body; added 3 characters in body; added 3 characters in body
Source Link
Arkajyoti Banerjee
Arkajyoti Banerjee
  • 246
  • 1
  • 8

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing SequenceSubsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Sequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?

(Just to add some substance, can it be shown there can exist such sequences, given any arbitrary value of $ N > 1 $?)

Source Link
Arkajyoti Banerjee
Arkajyoti Banerjee
  • 246
  • 1
  • 8

Proof of existence / non-existence of such a sequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Sequence is less than $ \displaystyle \lfloor \frac{N}{2} \rfloor $?

If yes, then give an example of such a sequence. Otherwise, can anyone present a proof that there cannot exist such a sequence?