大厂面试一般不会只考察单纯的哈希查表，而是会结合更复杂的数据结构来考或者美其名曰动态规划。先从简单的说，看完之后你会觉得动态规划也就是那样，之前“畏DP如虎”的心态完全没有必要。不多闲扯，先看题：
给定整数数列nums, 找到连续和最大的子数列，并返回数列和和，例：
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
其中[4,-1,2,1]加起来为6。
还是老套路，一个角标变两个角标而已，和上题一样，暴力两重循环必挂。那么正确的解法是怎样的呢？我们接下来说这道题背后考察的要点和面试官改编的思路。
我估计不少人需要O(n^3)才做得出来，如果我告诉你，这题的最优解法是O(n)，咋一看是不是不敢相信？我们要想不去暴力解，必须要 头脑冷静分析 ，这个子数列的一些特征。作为面试官，如果这题面试者不假思索地写答案，如果还写对了，十有八九是背答案，依然是不给过。
如果，我们确定了数组中的某一个元素作为子数列的元素，那么我们该如何找最大的子数列？我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？这时候，我们往前看一位，如果以A[i-1]作为尾数的子数列，加起来全是负值，那么这个以A[i]为尾数的最大子数列就是{A[i]}，只有自身一个元素；反之，如果和是正数，则是A[i-1]为尾数的子数列，拼上A[i]。那么以此类推，在一轮循环中，我们找到以A[i]为终点的子数列最大和，一轮循环过后，就得到我们的答案了。
举例：[−1, 1, −3, 4, −1, 2, 1, −5, 8]，以第一个数为终点，最大的子数列就是自己，最大和为-1，第二个数，因为arr[1]的前一个数arr[0]为终点的子数列是负数，所以以arr[1]为终点，最大子数列就是自己，和就是1，以此类推，直到最后一位。
在这里，前一位和后一位的联系就是上述的规则：如果以A[i-1]作为尾数的子数列，加起来全是负值，那么这个最大子数列就是{A[i]}，只有一个元素，反之，则是A[i-1]为尾数的子数列，拼上A[i]，用前一轮的结果，来推算下一个脚标的结果。
代码实现：
def max_subarray(A):
max_ending_here = max_so_far = A[0]
for x in A:
max_ending_here = max(x, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far