九度笔记之 1342：寻找最长合法括号序列II（25分）

题目1342：寻找最长合法括号序列II（25分）

时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：527
解决：216

题目描述：
假如给你一个由’(‘和’)’组成的一个随机的括号序列，当然，这个括号序列肯定不能保证是左右括号匹配的，所以给你的任务便是去掉其中的一些括号，使得剩下的括号序列能够左右括号匹配且长度最长，即最长的合法括号序列。
输入：
测试数据包括多个，每个测试数据只有一行，即一个随机的括号序列，该括号序列的长度保证不超过106。
输出：
对于每个测试案例，输出一个整数，表示最后剩下的最长合法括号序列长度。
样例输入：
(())()
(()样例输出：
6
2算法分析

一句话，从左到右看能找到几对括号。

利用Lnum表示在当前位置已经找个几个单身的‘（’，

当遇到‘（’,Lnum++；

当遇到‘）’,如果Lnum>0,表示前面有单身的‘（’，当前的‘）’和前面的一个'（'结为一对，少了一个单身的'('，所以Lnum减1。又因为新增加了一对‘（’，‘）’，所以maxLen+=2;

另外一个最长合法括号序列题，不过算法相差很大。见九度笔记之 1337：寻找最长合法括号序列

源程序

//============================================================================
// Name        : judo1342new.cpp
// Author      : wdy
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//similar to 1337
//similar to 1260
#include <iostream>
using namespace std;
 
void getMaxLen(std::string &s){
    std::string::size_type len = s.size();
    std::string::size_type pos = 0;
 
    int Lnum = 0;
    //int Rnum = 0;
    int maxLen  = 0;
    for(pos = 0;pos<len;pos++){
        if(s.at(pos)=='(')
            ++Lnum;
        else if(Lnum>0){
            --Lnum;
            maxLen+=2;
        }
    }//for
    std::cout<<maxLen<<std::endl;
}
 
void judo(){
    std::string s;
    while(std::cin>>s){
        getMaxLen(s);
    }
}
int main() {
    judo();
    //cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
    return 0;
}
 
/**************************************************************
    Problem: 1342
    User: KES
    Language: C++
    Result: Accepted
    Time:220 ms
    Memory:3052 kb
****************************************************************/

补充：软件开发 , C++ ,