(Analysis by Danny Mittal)
We will refer to the string of Us and Ds as s.
Subtask 1: N≤500
We can do DP. For each triple (j,k,u), our DP says whether there exists a subsequence of p1,…,pk consistent with s1…sj that ends in the number u. Transitions are constant time, so the runtime is O(N3).
Subtask 2: N≤5000
We can improve the DP from the previous subtask by noting that depending on whether sj+1 is U or D, it's optimal for the previous number in the subsequence to be as small or as large as possible. Therefore, our DP should find for each pair (j,k) both the smallest and the largest numbers such that there exists a subsequence of p1,…,pk consistent with s1…sj that ends in that number. Transitions are again constant time, so the runtime is O(N2).
Subtask 3: s is Us followed by Ds
Apply a standard LIS algorithm to find for each number the longest LIS ending in that number, as well as the longest LIS ending in that number that goes in reverse (starting from the end of p). Now let the number of Us in s be j. If there is no LIS of p with j+1, then we simply use the longest LIS that we found. Otherwise, find the first position in p where we have an LIS of length j+1, then use the longest reverse LIS that ends at or after that position to compute the answer.
The runtime is O(NlgN) using an appropriate LIS algorithm.
Subtask 4: No additional constraints
Intuitively, it makes sense for us to try to find the fastest (ending the earliest) subsequence of p consistent with each prefix of s, and build on that subsequence to find the fastest subsequence for the next prefix of s. Unfortunately, this idea doesn't even work for normal LIS (longest increasing subsequence), i. e. the case where s is UUUU..., because we can have a case like
p=[5,6,7,1,2,3,4]
where the fastest increasing subsequence of length 3 is [5,6,7], but the fastest one of length 4 is [1,2,3,4] which doesn't build on [5,6,7] at all.
However, it turns out that we can actually apply this idea when switching from contiguous segments of U to contiguous segments of D and vice versa. Specifically, suppose that sj is D, and the next x letters in s are U. If the fastest subsequence a of p consistent with s1…sj ends at index k, then consider finding the fastest LIS b of length x+1 in p considering only positions from k onwards. Say that b ends at position k′.
It's clear that the fastest subsequence of p consistent with s1…sj+x must end at or after position k′, because clearly it's not possible to find a subsequence consistent with s1…sj then an LIS of length x+1 that starts with the previous subsequence prior to k′.
However, we can actually use a and b to create a subsequence consistent with s1…sj+x that ends at position k′. If the last number aj in a and the first number b0 in b are the same, then we're done, because we can simply attach them at that number. Otherwise, note that it can't be that aj<b0, because otherwise we could add aj to the beginning of b and remove b's last element to get an LIS of length x+1 that ends earlier. Therefore, it must be that aj>b0. However, since sj is D, we can actually take a, remove aj, then add on b0, which is valid because aj−1>aj>b1 so the D is still satisfied, and now use b0 to glue together a and b.
Therefore, the end position of the fastest subsequence of p consistent with s1…sj+x is simply the end position of the fastest LIS of p considering only positions starting from the end position of the fastest subsequence consistent with s1…sj. All of this also applies when U and D are switched.
This means that our algorithm can work as follows. We divide s into its contiguous segments of U and D, and for each segment find the fastest LIS or LDS of the length of the segment +1 that only considers the part of p starting (inclusive) from the end of the previous LDS or LIS. We finish when we are unable to find an LIS or LDS of the appropriate length for some segment and simply use the longest one we were able to find for that last segment to compute the answer.
To find LISs and LDSs, we can simply apply one of the standard algorithms for finding LIS, but we have to be careful that the algorithm we use runs in time a function of the number of elements we consider, not a function of N, as there can potentially be many segments in s. An elegant choice given this constraint is the binary search tree algorithm for LIS, which is used in the Java code below.
Assuming our LIS algorithm runs in O(xlgx) where x is the number of elements we consider, the runtime of our overall algorithm is O(NlgN).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class UpDownSubsequence {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
char[] directions = in.readLine().toCharArray();
int k = 0;
int last = Integer.parseInt(tokenizer.nextToken());
while (tokenizer.hasMoreTokens() && k < directions.length) {
char direction = directions[k];
TreeSet<Integer> treeSet = new TreeSet<Integer>(direction == 'U' ? Comparator.naturalOrder() : Comparator.reverseOrder());
treeSet.add(last);
while (tokenizer.hasMoreTokens() && k < directions.length && directions[k] == direction) {
last = Integer.parseInt(tokenizer.nextToken());
Integer displaced = treeSet.higher(last);
if (displaced == null) {
k++;
} else {
treeSet.remove(displaced);
}
treeSet.add(last);
}
}
System.out.println(k);
}
}
