//
// Created by 罗炳国 on 2024/1/3.
//

#ifndef PFJ_CODE041_LONGESTVALIDPARENTHESES_H
#define PFJ_CODE041_LONGESTVALIDPARENTHESES_H

#include "commonHeader.h"

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 32 https://leetcode.cn/problems/longest-valid-parentheses/submissions/
 * */

class code041_longestValidParentheses {
public:
    int longestValidParentheses(string s) {
        int N = s.size();
        int ans = 0;
        if (N == 0)
            return ans;

        vector<int> dp(N, 0);

        for (int i = 1; i < N; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(')
                    dp[i] = i > 2 ? 2 + dp[i - 2] : 2;
                else { // ')'
                    if (i - dp[i - 1] - 1 >= 0 && s[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (i - dp[i - 1] - 2 >= 0)
                            dp[i] += dp[i - dp[i - 1] - 2];
                    }
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }

    void test() {
        string s("(()");
        int ans = longestValidParentheses(s);
        std::cout << s << ":" << ans << endl;

        s = "(()(())())";
        ans = longestValidParentheses(s);
        std::cout << s << ":" << ans << endl;

        s = ")()())";
        ans = longestValidParentheses(s);
        std::cout << s << ":" << ans << endl;

        s = "()()))))()()(";
        ans = longestValidParentheses(s);
        std::cout << s << ":" << ans << endl;

    }
};


#endif//PFJ_CODE041_LONGESTVALIDPARENTHESES_H