Заданный вопрос:



Строка скобок называется сбалансированной, если левая и правая скобки в строке могут быть правильно спарены. Например, строки(())» а также "() ()» оба сбалансированы, в то время как строка(() (» не сбалансирован.

Дана строка S длины п состоящий из скобок, предположим, что вы хотите найти самую длинную подпоследовательность S это сбалансировано. Используя динамическое программирование, спроектируйте алгоритм, который находит самую длинную сбалансированную подпоследовательность S вO (N ^ 3) время.

Мой подход:

Предположим, данная строка: S [1 2 ... n]

Допустимая подпоследовательность может заканчиваться на S [i], если S [i] == ')' то есть S [i] является закрывающей фигурной скобкой, и существует по крайней мере одна неиспользованная открывающая фигурная скобка, предшествующая S [i]. который может быть реализован в O (N).

#include
using namespace std;
int main(){
    string s;
    cin >> s;
    int n = s.length(), o_count = 0, len = 0;
    for(int i=0; i 0){
            ++len;
            --o_count;
        }
    }
    cout < len < endl;
    return 0;
}