1
$\begingroup$

In Jeff Erickson's Algorithms textbook, the chapter on Dynamic Programming asks you to "Describe an efficient algorithm to compute the length of the shortest oscillating supersequence of an arbitrary array A of integers".

A supersequence contains all of the elements from the original array X[1...n], and oscillating is defined as X [i] < X [i + 1] for all even i, and X [i] > X [i + 1] for all odd i.

However, I am not asking about the answer to this problem. I am just wondering if this question even is sound. How can you find a supersequence of a single array? Wouldn't the answer just be the length of the original array if all elements are oscillating? Else, 0. Usually, a supersequence is found between multiple arrays.

$\endgroup$
1
$\begingroup$

What about the array $[1, 3, 5]$? The supersequence $[0,1,0,3,0,5]$ is oscillating while the original sequence isn’t. In fact you can make an oscillating supersequence of any array by inserting $\min(arr)-1$ before every element of the original array.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.