Самая длинная подпоследовательность S, которая сбалансирована
Заданный вопрос:
Строка скобок называется сбалансированной, если левая и правая скобки в строке могут быть правильно спарены. Например, строки(())» а также "() ()» оба сбалансированы, в то время как строка(() (» не сбалансирован.
Дана строка 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;
}