Longest monotonically decreasing subsequence, with no consecutive elements included

Question

for example:

s = <6, 5, 4, 3, 2, 1>, s1 = <6, 4, 1>, s2 = <5, 2>, s3 = <5, 3, 2>

Given s as a sequence, s1 and s2 are the valid subsequences to be considered, but s3 is not because it contains a consecutive elements 3 and 2.

How do you find a longest such a subsequence so that it is monotonically decreasing in O(n^2)

I am aware of the version of the question that contains monotonic increase/ decrease.

But the additional condition here makes it difficult.

A trivial solution would be to start at i = n'th element as well as at j = (n-1)'th element, solve as if solving for longest monotonically decreasing subsequence with consideration that next element is at (i-2)'th and (j-2)'th respectively and compare the length of two at the end. This will still give the O(n^2), but does seem way too trivial.

Is there a better approach?

Your title says monotonically decreasing, but your body says monotonically non-decreasing. What are you looking for? — user2357112 supports Monica
...are you sure you know what "decrease" means? And why would "too trivial" be a reason to reject an algorithm that you think works? — user2357112 supports Monica
And why are you going for O(n^2) when standard algorithms for the longest increasing subsequence problem achieve O(n log n)? — user2357112 supports Monica

amit amit · Accepted Answer · 2017-12-08T07:44:35

D[i] = max { D[j] + 1 | a[i] < a[j], j < i + 1 } U {1}

Explanation: for each element a[i], your Dynamic Programming (DP) checks for all numbers that are before it and with lower value, but not adjacent - if the new number can be used to extend the best sequence. In addition, you have the option to start a new sequence (that's when the {1} comes to play).

Example: S = <6, 0, 5, 8, 4, 7, 6 >

D[1] = max { 1 } = 1  // sequence = <6>
D[2] = max {1} = 1  // sequence = <0>
D[3] = max {1, D[0] + 1 } = 2  // sequence = <6, 5>
D[4] = max {1} = 1  // sequence = <8>
D[5] = max{D[3] + 1, D[1] + 1, 1} = 3 // sequence = <6, 5, 4>
D[6] = max{D[4] + 1, 1} = 2  // sequence = <8, 7>
D[7] = max{D[4] + 1, 1} = 2  // sequence = <8, 6>

The algorithm runs in O(n^2), since calculating D[i] takes O(i) time. From sum of arithmetic progression, this sums to O(n^2) to calculate all.

When you are done calculating all D[.], you iterate through all of them, and find the maximal value. This is done in linear time.

Longest monotonically decreasing subsequence, with no consecutive elements included

1 Answers