UVa 10534

From Algorithmist
Jump to navigation Jump to search

UVa 10534 Wavio Sequence[edit]



You have the sequence of positive integers. You must find the length of longest Wavio Sequence. The Wavio Sequence of length is the sequence where first integers in this sequence makes a strictly increasing sequence and the last integers of this sequence makes a strictly decreasing sequence.


For each integer you can find the length of a strictly increasing sequence which end with this integer, and the length of a strictly decreasing sequence which start with this element. But if you do this by Dynamic Programming you got TL.

So, to makes the algorithm efficient you can used RMQ or Interval tree. You must convert all sequence in range (0,MMAX). Example, if you have sequence , then you convert this sequence in the sequence .

Then, for each integer X in convert sequence you want to know, what is the length of strictly increasing sequence, which end of this element. Do it with query L=RMQ(0,X-1). And then change the array: Change(X,L+1).

Do the same with the reverse of this sequence (longest decreasing sequence is the longest increasing sequence when this sequence reverse).

Then for each element of the convert sequence look the length of Wavio Sequence when this element is the max element in this sequence.


There is another solution of this problem with using the Longest Increasing Subsequence problem and Binary Search.


1 2 3 4 5 4 3 2 1 10
1 2 3 2 1 2 3 4 3 2 1 5 4 1 2 3 2 2 1
1 2 3 4 5