Well, you know the rule. Just quick recap here.

Looping through every character of string, checking only the ')', because '(' is not a valid end.

Two things could happen here,

- if previous character = '(', we need to update dp[], so dp[i] = dp[i-2] + 2;

a. i.e. i = 3 here, "()()", dp[3] = dp[1] + 2, since dp[1] = 2, so dp[3] = 2 + 2 = 4.

b. i.e. i = 3 here, "))()", dp[3] = dp[1] + 2, since dp[1] = 0, so dp[3] = 0 + 2 = 2. - else previous character = ')', then we have to check the character before the last valid expression which is at i - dp[i-1] - 1, if that is = '(', we have to update, dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2

a. i.e. i = 5 here, "()(())", dp[5] = dp[1] + dp[4] + 2, since dp[1] = 2 & dp[4] = 2, so dp[5] = 2 + 2 + 2 = 6.

a. i.e. i = 5 here, "))(())", dp[5] = dp[1] + dp[4] + 2, since dp[1] = 0 & dp[4] = 2, so dp[5] = 0 + 2 + 2 = 4.

One may ask how do we resolve the corner case, such as "()" or "))" ? There is no i-2 = -1 character here.

Well, just like linkedlist, we can add a dummy character in the beginning.

I used 'x' here, but if you feel like you have to conform the rule that string only contains '(' and ')', you can use ')'. :)

This makes the code extra clean.

```
public static int longestValidParentheses(String s) {
if (s == null) return 0;
int[] dp = new int[s.length() + 1];
s = 'x' + s;
int max = 0;
char[] chars = s.toCharArray();
for (int i = 2; i < chars.length; i++) {
if (chars[i] == ')') {
if (chars[i - 1] == '(') dp[i] = dp[i - 2] + 2;
else if (chars[i - dp[i - 1] - 1] == '(') dp[i] = dp[i - dp[i - 1] - 2] + dp[i - 1] + 2;
max = Math.max(max, dp[i]);
}
}
return max;
}
```