public int longestValidParentheses_4(String s) { // DP solution, take advantage of the computed DP value, it is the distance to the index we want to look at
		int [] DP = new int[s.length()];
		int res = 0;
		for(int i = 0; i < DP.length; ++i){
			if(s.charAt(i) == ')' && i > 0){
				int j = i - 1 - DP[i-1];
				if(j >= 0 && s.charAt(j) == '('){
					DP[i] = DP[i-1] + 2;
                    if(j - 1 >= 0) DP[i] += DP[j-1];
                    res = Math.max(res, DP[i]);
				}
			}
		}
		return res;
	}