題目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
****************************************************************/
