1+ /*
2+ Author: King, wangjingui@outlook.com
3+ Date: Dec 20, 2014
4+ Problem: Longest Valid Parentheses
5+ Difficulty: Easy
6+ Source: https://oj.leetcode.com/problems/longest-valid-parentheses/
7+ Notes:
8+ Given a string containing just the characters '(' and ')', find the length of the longest valid
9+ (well-formed) parentheses substring.
10+ For "(()", the longest valid parentheses substring is "()", which has length = 2.
11+ Another example is ")()())", where the longest valid parentheses substring is "()()",
12+ which has length = 4.
13+
14+ Solution: O(n).
15+ */
16+
17+ public class Solution {
18+ public int longestValidParentheses_1 (String s ) {
19+ Stack <Integer >stk =new Stack <Integer >();
20+ int res =0 ,count =0 ;
21+ for (int i =0 ;i <s .length (); ++i ) {
22+ if (s .charAt (i ) =='(' ) {
23+ stk .push (count );
24+ count =0 ;
25+ }else if (stk .empty () ==false ) {
26+ count += (1 +stk .pop ());
27+ res =Math .max (res ,count );
28+ }else {
29+ count =0 ;
30+ }
31+ }
32+ return res *2 ;
33+ }
34+ public int longestValidParentheses (String s ) {
35+ int n =s .length ();
36+ if (n <=1 )return 0 ;
37+ int res =0 ;
38+ int []f =new int [n ];
39+ for (int i =n -2 ;i >=0 ;i --){
40+ int match =i +f [i +1 ] +1 ;
41+ if (match <n &&s .charAt (i )=='(' &&s .charAt (match )==')' ){
42+ f [i ]=f [i +1 ]+2 ;
43+ if (match +1 <n )f [i ]+=f [match +1 ];
44+ }
45+ res =Math .max (res ,f [i ]);
46+ }
47+ return res ;
48+ }
49+ }
