給定一個字符串s，其中只包含字符'('和')'，需要找出其中最長的有效括號子串的長度。本篇文章將介紹如何通過動態(tài)規(guī)劃算法來實現(xiàn)這一目標。 實現(xiàn)算法步驟 創(chuàng)建一個數(shù)組dp，其中第i個元素表示

給定一個字符串s，其中只包含字符'('和')'，需要找出其中最長的有效括號子串的長度。本篇文章將介紹如何通過動態(tài)規(guī)劃算法來實現(xiàn)這一目標。

實現(xiàn)算法步驟

1. 創(chuàng)建一個數(shù)組dp，其中第i個元素表示字符串s中第i個字符對應的有效括號長度。
2. 通過動態(tài)規(guī)劃思想，填充上述dp數(shù)組：
   • 如果s[i]')'且s[i-1]'('，即括號串的樣式為"(...)"，則dp[i]dp[i-2] 2。
   • 如果s[i]')'且s[i-1]')'，即括號串形如"...)..."，如果s[i-dp[i-1]-1]'('，那么dp[i]dp[i-1] dp[i-dp[i-1]-2] 2。

編寫本地測試主方法

為了驗證算法的正確性，可以編寫一個本地測試方法來觀察控制臺輸出結果是否符合預期。

運行本地測試主方法

執(zhí)行本地測試主方法，并觀察控制臺輸出結果，確保算法按照預期工作。

算法復雜度分析

整個算法只需遍歷一遍字符串s，因此時間復雜度為O(n)，其中n是括號字符串的長度。同時需要創(chuàng)建一個長度為n的數(shù)組dp，所以空間復雜度也是O(n)。