這題目真是越做越難了。
但其實只是思路很難想到，一旦會了方法就很好做。
但問題就在方法太難想了……
思路還是只要遍歷一遍數組，維護動態規劃數組記錄截止至目前位置選取該元素的情況下有效括號的最大值。
光是知道這個還不夠，看了答案才知道每次可以取兩個元素。
具體來說分三種情況：
- 當前元素為‘(’，則最后取該元素時一定沒有有效括號，所以元素取為0.
- 當前元素為')'，并且前面有元素且上一個元素為'('，這種情況就等于上上個元素數組維護的值加上2。
- 當前元素為')'，并且前面有元素且上一個元素為')'，這種情況就要追溯到前面有效括號再之前的元素，如果前面有有效括號并且前面的有效括號前面是'('，這時當前元素前一個元素維護的值恰好記錄的那個有效括號的長度，通過減去這個有效長度再減1（原本查看上一個元素也要減1，所以一共減2）就可以得到前面有沒有相匹配的'('，于是就可以得到當前維護的數=前面有效括號的長度+2（若當前右括號與前面左括號相匹配）
狀態轉移方程如上。
class Solution {
public:int longestValidParentheses(string s) {if(s.size()==0) return 0;vector<int> array(s.size()+1,0);int result=0;for(int i=2;i<=s.size();i++){if(s[i-1]=='(') array[i]=0;else if(s[i-2]=='('&&s[i-1]==')') array[i]=array[i-2]+2;else if(s[i-2]==')'&&s[i-1]==')'&&i>=array[i-1]+2&&s[i-array[i-1]-2]=='(') array[i]=array[i-array[i-1]-2]+array[i-1]+2;result=max(result,array[i]);}return result;}
};
)
