微软面试真题+面试官改编 leetcode 思路（动态规划篇）

[longSwordMan]

在上一个帖子主要和大家分享了刷 leetcode 的正确姿势，收到了很不错的反馈，所以应邀继续给大家进行深入的专栏分享。今天主要是动态规划篇，接下来还会陆续更新链表篇，哈希篇等，大家可以关注一下。如果在此过程中有问题希望能够与我深入探讨，可以添加微信 longswordMAN 进行交流。那我们话不多说，开始我们的动态规划专题讲解。

大厂面试一般不会只考察单纯的哈希查表，而是会结合更复杂的数据结构来考或者美其名曰动态规划。先从简单的说，看完之后你会觉得动态规划也就是那样，之前“畏 DP 如虎”的心态完全没有必要。

言归正传，先看题：给定整数数列 nums, 找到连续和最大的子数列，并返回数列和和。

举个例子： Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 其中[4,-1,2,1]加起来为 6 。

还是老套路，一个角标变两个角标而已，和上题一样，暴力两重循环必挂。

那么正确的解法是怎样的呢？背后考察的要点和面试官改编的思路又是什么样呢？大家可以先思考一下，中午 12 点我会在评论区与大家分享我的见解。

[babyformula]

贪心算法就好了吧

[doudou1523102]

小板凳做好

[B1ankCat]

最大连续子数组问题，可以用分治，也可以记录前面处理过的最大子数组然后和 j+1 作对比实现θ(n)的线性复杂度，咦这里是动态规划，走错了走错了

[realkenshinji]

kadane’s algorithm

[longSwordMan]

@B1ankCat 这么做空间上不是最优哦

[longSwordMan]

@babyformula 是的，但要知其所以然

[longSwordMan]

我估计不少人需要 O(n^3)才做得出来，如果我告诉你，这题的最优解法是 O(n)，咋一看是不是不敢相信？我们要想不去暴力解，必须要头脑冷静分析，这个子数列的一些特征。作为面试官，如果这题面试者不假思索地写答案，如果还写对了，十有八九是背答案，依然是不给过。

[longSwordMan]

如果，我们确定了数组中的某一个元素作为子数列的元素，那么我们该如何找最大的子数列？我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？这时候，我们往前看一位，如果以 A[i-1]作为尾数的子数列，加起来全是负值，那么这个以 A[i]为尾数的最大子数列就是{A[i]}，只有自身一个元素；反之，如果和是正数，则是 A[i-1]为尾数的子数列，拼上 A[i]。那么以此类推，在一轮循环中，我们找到以 A[i]为终点的子数列最大和，一轮循环过后，就得到我们的答案了。

[longSwordMan]

举例：[−1, 1, −3, 4, −1, 2, 1, −5, 8]，以第一个数为终点，最大的子数列就是自己，最大和为-1，第二个数，因为 arr[1]的前一个数 arr[0]为终点的子数列是负数，所以以 arr[1]为终点，最大子数列就是自己，和就是 1，以此类推，直到最后一位。