Up Down Subsequence

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?

Consider using LIS to improve the complexity.

I fail to see how the binary search used in the module would apply here. My recurrence is basically the same though.

Have you considered reading the editorial?

No?

You should probably do that then…

If you haven’t already read the editorial maybe these hints might help without completely giving it away consider using more than one RMQ segtree, considering how many states a subsequence ending on a number can have that matter

consider using more than one RMQ segtree

I’m not using any right now LOL, but thanks for the hint!

Thanks for the advice- I finally managed to solve it!

Yay!