# LeetCode - 0032. Longest Valid Parentheses
### 題目網址：https://leetcode.com/problems/longest-valid-parentheses/
###### tags: `LeetCode` `Hard` `動態規劃（Dynamic Programming）`

/*
    -LeetCode format-
    Problem: 32. Longest Valid Parentheses
    Difficulty: Hard
    
    by Inversionpeter
*/



static const auto Initialize = []{
    ios::sync_with_stdio(false); cout.tie(nullptr);
    return nullptr;
}();

int DP[30005];

class Solution {
public:
    int longestValidParentheses(string s) {
        int maximum = 0;
        fill(DP, DP + s.size() + 1, 0);
        for (int i = 1; i < int(s.size()); ++i)
            if (s[i] == ')' && i > DP[i] && s[i - DP[i] - 1] == '(') {
                DP[i + 1] = DP[i] + DP[i - DP[i] - 1] + 2;
                maximum = max(maximum, DP[i + 1]);
            }
        return maximum;
    }
};