32 Longest Valid Parentheses

class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) return 0;
        int[] dp = new int[s.length()];

        int ans = 0;
        for (int i = 1; i < s.length(); i++){
            if (s.charAt(i) == ')'){
                //System.out.println("i: " + i + " dp: " + Arrays.toString(dp));
                if (s.charAt(i - 1) == '('){
                    dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
                }
                else if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                    dp[i] = i - dp[i - 1] - 2 >= 0 ? dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 : dp[i - 1] + 2;
                }
                ans = Math.max(ans, dp[i]);
            }
        }

        return ans;
    }
}

376 Wiggle Subsequence

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length < 2) return nums.length;

        int[] up = new int[nums.length];
        int[] down = new int[nums.length];

        up[0] = down[0] = 1;
        for (int i = 1; i < nums.length; i++){

            if (nums[i] > nums[i - 1]){
                up[i] = down[i - 1] + 1;
                down[i] = down[i - 1];
            }
            else if (nums[i] < nums[i - 1]){
                down[i] = up[i - 1] + 1;
                up[i] = up[i - 1];
            }
            else{
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }

        return Math.max(up[nums.length - 1], down[nums.length - 1]);
    }
}