有効な括弧の最大長さ Longest valid Parentheses

Quiz

https://practice.geeksforgeeks.org/problems/longest-valid-parentheses/0

Submission

https://practice.geeksforgeeks.org/viewSol.php?subId=14381873&pid=1247&user=peroon

例

4
(()(
()()((
((()()())))
()(())(

2
4
10
6

Code

ll maxLen(string s){
  ll L = s.size();
  stack<ll> st;
  st.push(-1);

  ll len = 0;

  FOR(i, 0, L){
    if(s[i]=='('){
      st.push(i);
    }
    else{
      st.pop();

      if(!st.empty()){
        len = max(len, i - st.top());
      }
      else{
        st.push(i);
      }
    }
  }
  return len;
}

感想

• DP使いそう、と思わせてスタックでした
• 解けなかったので解法を見た。スタックの使い方が天才的・・・