题解 | #括号字符串的最长有效长度#

括号字符串的最长有效长度

http://www.nowcoder.com/practice/335acafb6d5141b7873c4b0f24d53c57

//经典动态规划
//申请一个同样长度的dp表
//dp[i]的含义为以i为结尾的最长有效长度是多少
#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;
    cin>>str;
    int len=-1;
    int *dp=new int[str.size()-1];
    dp[0]=0;
    for(int i=1;i<str.size();i++){
        if(str[i]=='('){//以(结尾的长度必定为0
            dp[i]=0;
        }
        else{//如果dp[i]=')'
            if(str[i-1]=='('){//此时正好能凑出来一对括号
                dp[i]+=2;
                dp[i]+=i-2>=0?dp[i-2]:0;
                len=len>dp[i]?len:dp[i];
            }
            else{//此时说明str[i-1]==')'
                if(i-dp[i-1]-1>=0){
                    if(str[i-dp[i-1]-1]=='('){
                        dp[i]=dp[i]+2+dp[i-1];
                        dp[i]+=i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0;
                        len=dp[i]>len?dp[i]:len;
                    }
                }
            }
        }
    }
    cout<<len<<endl;
    return 0;
}
全部评论

相关推荐

06-25 16:25
梧州学院 Java
愿汐_:项目介绍那么长,然而你做了啥就一句话?
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务