I’m doing this problem, and my code is as follows:
import java.io.*;
import java.util.*;
public class UpDownSubseq {
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int len = Integer.parseInt(read.readLine());
// just gonna assume this is a permutation
int[] arr = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
String relStr = read.readLine();
assert arr.length == len && relStr.length() == len - 1;
int[] best = new int[len];
Arrays.fill(best, -1);
best[0] = arr[0];
for (int i = 1; i < len; i++) {
for (int j = len - 1; j >= 0; j--) {
if (j > 0) {
// check if it satisfies the previous requirement
char req = relStr.charAt(j - 1);
if (best[j - 1] == -1
|| (req == 'U' && arr[i] < best[j - 1])
|| (req == 'D' && arr[i] > best[j - 1])) {
continue;
}
}
if (j < len - 1) {
// if the next char is a U, try to minimize it
if (relStr.charAt(j) == 'U') {
best[j] = best[j] == -1 ? arr[i] : Math.min(best[j], arr[i]);
} else if (relStr.charAt(j) == 'D') {
// else, try to maximize it
best[j] = best[j] == -1 ? arr[i] : Math.max(best[j], arr[i]);
}
} else {
// at the last element, it doesn't matter
best[j] = arr[i];
}
}
}
// output the longest sequence that has been made
for (int i = len - 1; i >= 0; i--) {
if (best[i] != -1) {
System.out.println(i);
break;
}
}
}
}
Right now it’s an \mathcal{O}(N^2) algorithm that tries to maximize or minimize certain array elements so the succeeding element has an easier time being found.
However, this only passes 8/22 test cases, and I’m trying to optimize this to run in linear time. Does this require a complete rethink of the algorithm, or is there some optimization I can use?