Рассмотрим B как последовательность символов группировки (,), [,], {и}. B называется сбалансированной последовательностью, если она имеет длину 0 или B имеет одну из следующих форм: {X} Y или [X] Y или {X} Y, где X и Y сами сбалансированы. Пример для Balanced: () - {[] ()} [] - ...

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

Например, если ввод() {([)] {(])}} [] одна из подпоследовательностей максимальной длины() {[] {()}} []

Я почти уверен, что решение - DP, но в любом случае я решаю его, я нахожу примеры, в которых мой алгоритм не работает. есть только один подход, в котором я уверен, это комбинация DP и Divide and Conquer. Но это неэффективно, потому что в любом случае часть D & C будет снова и снова решать некоторые накладывающиеся проблемы.