最大子数组之和问题是 CLRS 上讲解分治算法的一道例题。由 $O(n\log(n))$ 的分治算法再到 $O(n)$ 的动态规划算法,都有很好的示范作用。
[LC42/84] Trapping Rain Water / Largest Rectangle in Histogram / 动态规划 / 双指针
这两题分别有不同的解法,但它们都可以用一种基于栈的方法来实现一次遍历计算结果。这种方法刚看到的时候不是很理解,思考后总结出其核心思想——确定迭代的每个步骤的「子任务」。这个选取的子任务通过循环迭代计算后,就可综合为最终结果(例如取最大/小值)。
[LC32] Longest Valid Parentheses / 动态规划
Longest Valid Parentheses - LeetCode
Given a string containing just the characters
'('
and')'
, find the length of the longest valid (well-formed) parentheses substring.
For"(()"
, the longest valid parentheses substring is"()"
, which has length = 2.
Another example is")()())"
, where the longest valid parentheses substring is"()()"
, which has length = 4.
[LC22] Generate Parentheses / 回溯
Generate Parentheses - LeetCode
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.