最长有效括号

- 研究最优策略的最后一步
- 化为子问题2、转移方程
    - 根据子问题定义得到
3、初始条件和边界情况
4、计算顺序

public class Solution {
    private int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        int size = chars.length;
        int[] dp = new int[size];
        int maxVal = 0;
        for (int i = 1; i < size; i++) {
            if (chars[i] == ')') {
                if (chars[i - 1] == '(') {
                    dp[i] = 2;
                    if (i - 2 > 0) {
                        dp[i] = dp[i] + dp[i - 2];
                    }
                } else if (dp[i - 1] > 0) {
                    if ((i - dp[i - 1] - 1) >= 0 && chars[i - dp[i - 1] - 1] == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if ((i - dp[i - 1] - 2) >= 0) {
                            dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                        }
                    }
                }
            }
            maxVal = Math.max(maxVal, dp[i]);
        }
        return maxVal;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = ")()())";
        int result = solution.longestValidParentheses(s);
        System.out.println("result = " + result);
    }
}