/*
**  This question need to pay attention to at leat three valid parentheses situations:
**      valid parentheses inside of other valid parentheses: ((()))
**      valid parentheses next to other other valid parentheses: ()()()
**      and combination of above two: ()(())
*/

#include <string>
#include <stack>

using namespace std;

int LongestValidParentheses(string& s)
{
    int longest = 0;
    int length = s.size();
    stack<size_t> iStack; //stack for index of left parenthesis in string
    stack<size_t> eStack; //stack for the end index of valid parentheses
    stack<size_t> lStack; //stack for length of valid parentheses associated in eStack
    int offset;

    for (int i = 0; i < length; ++i)
    {
		//push left parenthesis
        if (s[i] == '(')
		{
			iStack.push(i);
		}   

        else if (!iStack.empty()) //meat a matched right parenthesis
        {
            size_t iLeft = iStack.top();
			//offset of these matched parentheses
            offset = i - iLeft + 1;

            //pop out all saved valid parentheses that are 
            //just inside of current found valid parentheses
            while(!eStack.empty() && iLeft < eStack.top())
            {
                eStack.pop();
                lStack.pop();
            }

            //former valid parentheses is just next to current one
            //join them together
            if(!eStack.empty() && eStack.top() == iLeft-1)
            {
                offset += lStack.top();

                eStack.top() = i;
                lStack.top() = offset;
            }
            //eStack is empty or the former valid parentheses 
            //is not next to current one
            else 
            {
                eStack.push(i);
                lStack.push(offset);
            }

            if (offset > longest) longest = offset;

			iStack.pop();
        }
        //else invalid right parenthesis ')' as it match nothing
	}
	return longest;
}


#include <iostream>

#include <list>
#include <utility>
using namespace std;



int main(int argc, char** argv)
{
	string parentheses1 = "()(()(())";
	string parentheses2 = ")()())";
	
	cout << LongestValidParentheses(parentheses1) << '\n';
	cout << LongestValidParentheses(parentheses2) << '\n';
	return 0;
}