Leetcode Longest Valid Parentheses

错误代码：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int longestValidParentheses(string s)
 6 {
 7     int i = 0;
 8     int L = s.length();
 9     int j;
10     int max = 0;
11     while (i < L)
12     {
13         int left = 0;
14         int right = 0;
15         if (s[i] == '(')
16         {
17             left++;
18             j = i + 1;
19             int index = i-1;
20             while (j<L&&left >= right)
21             {
22                 if (left == right)
23                     index = j-1;
24                 if (s[j] == '(')
25                     left++;
26                 else
27                     right++;
28                 j++;
29             }
30             if (right >= left)
31             {
32                 if (left*2>max)
33                     max = left * 2;
34                 i = j;
35             }
36             else
37             {
38                 if (index == i - 1)
39                     ;
40                 else
41                 {
42                     int leftSum = index - i + 1;
43                     int rightSum = j - i - (left - right) - leftSum;
44                     if (leftSum > max)
45                         max = leftSum;
46                     if (rightSum > max)
47                         max = rightSum;
48                     if (leftSum > rightSum)
49                         i = index;
50                     else
51                         i = j;
52                 }
53             }
54         }
55         i++;
56     }
57     return max;
58 }
59 
60 int main()
61 {
62     string s = "(()(((()";
63     cout << longestValidParentheses(s) << endl;
64 }

View Code

这个题目是一个一维动态规划问题：

参考自：http://blog.csdn.net/a83610312/article/details/8639790

代码：

 1 #include<iostream>
 2 
 3 using namespace std;
 4 
 5 int longestValidParentheses(string s)
 6 {
 7     int L = s.length();
 8     int *flag = new int[L+1];
 9     memset(flag, 0, sizeof(int)*L);
10     int i = L;
11     while (i >= 0)
12     {
13         if (s[i] == '(')
14         {
15             int j = i + 1;
16             while (j < L&&flag[j]>0)
17                 j = flag[j] + 1;
18             if (s[j] == ')')
19                 flag[i] = j;
20             else
21                 flag[i] = -1;
22         }
23         i--;
24     }
25     int max = 0;
26     i = 0;
27     while (i < L)
28     {
29         int j = i;
30         while (j<L&&flag[j] > 0)
31         {
32             j = flag[j] + 1;
33         }
34         if (j - i > max)
35             max = j - i;
36         i = j + 1;
37     }
38     return max;
39 }
40 
41 int main()
42 {
43     string s = ")()())";
44     cout << longestValidParentheses(s) << endl;
45     return 0;
46 }

这里面主要说一下，16~21行。这里的方式是先寻找位置，在判断。这种方法很很好比遍寻找边判断要简单更省时间。