Самая длинная «подпоследовательность» сбалансированных скобок

Поскольку кто-то другой опубликовал ответ, вот O(n) ответ на один запрос с O(1) пробелом. Сохраняйте сбалансированное количество скобок и указатели на последнюю открытую и последнюю закрытую скобку. Пока вы не закончите строку, сканируйте вперед последнюю открытую строку, чтобы найти другую открытую скобку. Затем просканируйте вперед от максимума последней открытой и последней закрытой скобки, чтобы найти следующую закрытую скобку. Если вы найдете пару таким образом, увеличьте количество сбалансированных скобок. Когда вы дойдете до конца строки, у вас будет правильный счет, даже если вы неправильно соединили парные скобки.

На самом деле может быть несколько максимальных подпоследовательностей сбалансированных скобок. Но если вы возьмете любую максимальную подпоследовательность сбалансированных скобок и замените каждую открытую скобку самой левой открывающей скобкой, а затем каждую закрывающую скобку самой левой из возможных открытых скобок, результатом будут те, которые вы нашли. (Доказательство оставлено читателю в качестве поучительного упражнения.)

Вот псевдокод.

parens = 0
last_open = 0
last_closed = 0
while last_open < len(str) && last_closed < len(str):
    if str[last_open] == ')':
        # We are looking for the next open paren.
       last_open += 1
    elif last_closed < last_open:
       # Start our search for a last closed after the current char
       last_closed = last_open + 1
    elif str[last_closed] == '(':
       # still looking for a close pair
       last_closed += 1
    else:
       # We found a matching pair.
       parens += 1
       last_open += 1
# and now parens has the correct answer.

И затем у нас есть проблема со многими запросами диапазона. Оказывается, чтобы сделать это быстро, требуется O(n) предварительных вычислений и O(n) места, а каждый запрос диапазона будет занимать O(log(n)) времени.

Вот подсказка для этой проблемы. Предположим, что у нас есть 2 блока A и B рядом друг с другом. Каждый из которых внутри имеет некоторое количество сбалансированных подпоследовательностей скобок, некоторое количество дополнительных открытых скобок, доступных справа, и некоторое количество дополнительных закрывающих скобок, доступных слева. Тогда объединенный блок C имеет следующее:

C.balanced = A.balanced + B.balanced + min(A.open, B.close)
C.open = B.open + max(A.open - B.close, 0)
C.close = A.close + max(B.close - A.open, 0)

Я оставляю вам задачу выяснить, какой набор блоков нужно предварительно вычислить, чтобы иметь возможность вычислить любой блок за время O(log(n)).

Я опишу решение O (n)

Во-первых, у нас есть массив dp[n] для каждой позиции i , если i является закрывающей скобкой ), dp[i] будет хранить самую дальнюю позицию, которая образует допустимую последовательность скобок, заканчивающуюся на i.

Мы поддерживаем стек, в котором отслеживаются открытые скобки и их положение. Поэтому, если мы встречаем открытую скобку, мы помещаем ее в стек вместе с ее местоположением, а если мы встречаем закрывающую скобку, мы извлекаем последнюю открытую скобку и обновляем массив dp.

• dp[i] = min (position of open bracket, dp[position of open bracket - 1] ), это проверит, есть ли перед открывающей скобкой закрывающая скобка, если да, то улучшаем dp[i]

Таким образом, ответом будет наибольшее значение между i - dp[i]

Java-код:

    public static void main(String[] args) {
    String val = "))(()(())))(())";// Which store the parentheses sequence
    int[] dp = new int[val.length()];
    Arrays.fill(dp, -1);

    Stack<Integer> stack = new Stack();
    for (int i = 0; i < val.length(); i++) {
        char c = val.charAt(i);
        if (c == '(')
            stack.push(i);
        else if (!stack.isEmpty()) {
            int v = stack.pop();
            dp[i] = v;
            if (v > 0 && val.charAt(v - 1) == ')')
                if (dp[v - 1] != -1)
                    dp[i] = dp[v - 1];
        }
    }
    int result = 0;
    for (int i = 0; i < val.length(); i++){
        if (dp[i] != -1){
            System.out.println(val.substring(dp[i] , i + 1));

            result = Math.max(result, i - dp[i] + 1);
        }
    }
    System.out.println(result);
}

Вывод:

()
()
()(())
(()(()))
()
(())
8