九度笔记之 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 
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;pos0){
            --Lnum;
            maxLen+=2;
        }
    }//for
    std::cout<>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
****************************************************************/