Find Longest valid Parentheses Length [ Google ]

Problem:

Given a string consisting of opening and closing parenthesis, find length of the longest valid parenthesis sub string.[Courtesy: geeksforgeeks]

Problem Link

Solution: The problem can be solved with DP approach . And also as counting the left and right parenthesis from left to right.If the left parenthesis count is less than the right parenthesis count , then it means that validity of the parsed string  is invalid from this point. Find the longest valid length when left and right counts are equal . Start counting again left and right parenthesis count from 0 when left becomes less than right count.

Do the above approach from right to left of the string again.

#include <stdio.h>
#include <stack>
#include <string>
#include <iostream>
using namespace std;

int main() {
	//code
	int t;
	
	scanf("%d",&t);
	while(t--)
	{
		string s;
		cin>>s;
		int len=0;
		int max_len=0;
		int max_push_count=0;
		bool disConnected;
		int left=0,right=0;
		
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='(')
			{
				left+=1;
			}
			if(s[i]==')')
			{
				right+=1;
			}
			if(left==right)
			{
				max_len = (max_len<(left*2)?(left*2):max_len);
			}
			if(left<right)
			{
				left=0;
				right=0;
			}
		}
		left=0;right=0;
		for(int i=s.size()-1;i>=0;i--)
		{
			if(s[i]==')')
			{
				left+=1;
			}
			if(s[i]=='(')
			{
				right+=1;
			}
			if(left==right)
			{
				max_len = (max_len<(left*2)?(left*2):max_len);
			}
			if(left<right)
			{
				left=0;
				right=0;
			}
		}
		
		cout<<max_len<<endl;
	}
	return 0;
}

DP approach:

#include <stdio.h>
#include <queue>
#include <string>
#include <queue>
#include <iostream>
using namespace std;
/*
Input:
2
((()
)()())

Output:
2
4

)(() ans=2
()(((()()) ans=6

*/

int dp[10005];

int main() {
	//code
	int t;
	string s;
	int MX;
	cin>>t;
	while(t--)
	{
		cin>>s;
		
		for(int i=0;i<10005;i++)
		    dp[i]=0;
		if(s[1]==')' && s[0]=='(')
		    dp[1]=2;
		if(s[1]==')' && s[0]==')')
		    dp[1]=0;
		if(s[1]=='(')
		    dp[1]=0;
		MX=dp[1];
		for(int i=2;i<s.size();i++)
		{
			if(s[i]==')' && s[i-1]=='(')
			    dp[i]=dp[i-2]+2;
			if(s[i]==')' && s[i-1]==')')
			{
			    if(s[i-dp[i-1]-1]=='(')
			        dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2];
			}
			if(dp[i]>MX)
			MX=dp[i];
		}
		cout<<MX<<endl;
	}
	return 0;
}