S 的最长平衡子序列

给出的问题：

一串括号据说是 如果字符串中的左括号和右括号可以正确配对，则为平衡。例如，字符串“(())”和“()()”都是平衡的，而字符串“(()(”则不是 均衡。
给定一个字符串S长度n由括号组成，假设你想找到最长的子序列S这是平衡的。使用动态规划，设计一个算法来找到最长平衡子序列S in O(n^3) time.

我的做法：
假设给定字符串：S[1 2 ... n]
有效的子序列可以以 S[i] 结束，当且仅当 S[i] == ')' 即 S[i] 是右大括号，并且 S[i] 之前至少存在一个未使用的左大括号。可以在 O(N) 内实现。

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

我尝试了几个测试用例，它们似乎运行良好。我在这里错过了什么吗？如果没有，那么我怎样才能设计一个O(n^3)动态规划这个问题的解决方案？

这是定义子序列 http://en.wikipedia.org/wiki/Subsequence我正在使用的。

Thanks!

For O(n^3)我认为 DP 这应该有效：

dp[i, j] = longest balanced subsequence in [i .. j]
dp[i, i] = 0
dp[i, i + 1] = 2 if [i, i + 1] == "()", 0 otherwise

dp[i, j] = max{dp[i, k] + dp[k + 1, j] : j > i + 1} in general

这可以类似于如何实现最优矩阵链乘法 http://en.wikipedia.org/wiki/Matrix_chain_multiplication is.

你的算法对我来说似乎也是正确的，例如这个问题：

http://xorswap.com/questions/107-implement-a-function-to-balance-parentheses-in-a-string-using-the-minimum-nu http://xorswap.com/questions/107-implement-a-function-to-balance-parentheses-in-a-string-using-the-minimum-nu

其中解决方案与您的基本相同。

您只是忽略了额外的括号，所以我不明白为什么它不起作用。