One-dimensional DP:
- Clear thinking is the most important because each question varies greatly.
- Longest Valid Parentheses. Find the length of the longest valid substring of a string that contains only “(“ and “)”. Valid means that all the parentheses in the substring match correctly.
- Maximum Subarray. What is the maximum value of a one-dimensional array (A[0], A[1],…,A[n-1], A[n]) of n integer elements with many consecutive subarrays, where the sum of the arrays is the maximum value?
