微软面试真题+面试官改编 leetcode 思路（动态规划篇）
longSwordMan · 2020-06-17 10:36:44 +08:00 · 2129 次点击这是一个创建于 1618 天前的主题，其中的信息可能已经有所发展或是发生改变。
在上一个帖子主要和大家分享了刷 leetcode 的正确姿势，收到了很不错的反馈，所以应邀继续给大家进行深入的专栏分享。今天主要是动态规划篇，接下来还会陆续更新链表篇，哈希篇等，大家可以关注一下。如果在此过程中有问题希望能够与我深入探讨，可以添加微信 longswordMAN 进行交流。那我们话不多说，开始我们的动态规划专题讲解。
大厂面试一般不会只考察单纯的哈希查表，而是会结合更复杂的数据结构来考或者美其名曰动态规划。先从简单的说，看完之后你会觉得动态规划也就是那样，之前“畏 DP 如虎”的心态完全没有必要。
言归正传，先看题：给定整数数列 nums, 找到连续和最大的子数列，并返回数列和和。
举个例子： Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 其中[4,-1,2,1]加起来为 6 。
还是老套路，一个角标变两个角标而已，和上题一样，暴力两重循环必挂。
那么正确的解法是怎样的呢？背后考察的要点和面试官改编的思路又是什么样呢？大家可以先思考一下，中午 12 点我会在评论区与大家分享我的见解。
 |
1
babyformula 2020-06-17 10:59:58 +08:00
贪心算法就好了吧
|
 |
2
doudou1523102 2020-06-17 11:39:45 +08:00
小板凳做好
|
 |
3
B1ankCat 2020-06-17 11:57:25 +08:00
最大连续子数组问题，可以用分治，也可以记录前面处理过的最大子数组然后和 j+1 作对比实现θ(n)的线性复杂度，咦这里是动态规划，走错了走错了
|
 |
4
realkenshinji 2020-06-17 12:19:01 +08:00 via iPhone
kadane’s algorithm
|
 |
5
longSwordMan OP @B1ankCat 这么做空间上不是最优哦
|
|
6
longSwordMan OP @babyformula 是的，但要知其所以然
|
|
7
longSwordMan OP 我估计不少人需要 O(n^3)才做得出来，如果我告诉你，这题的最优解法是 O(n)，咋一看是不是不敢相信？我们要想不去暴力解，必须要头脑冷静分析，这个子数列的一些特征。作为面试官，如果这题面试者不假思索地写答案，如果还写对了，十有八九是背答案，依然是不给过。
|
|
8
longSwordMan OP 如果，我们确定了数组中的某一个元素作为子数列的元素，那么我们该如何找最大的子数列？我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？这时候，我们往前看一位，如果以 A[i-1]作为尾数的子数列，加起来全是负值，那么这个以 A[i]为尾数的最大子数列就是{A[i]}，只有自身一个元素；反之，如果和是正数，则是 A[i-1]为尾数的子数列，拼上 A[i]。那么以此类推，在一轮循环中，我们找到以 A[i]为终点的子数列最大和，一轮循环过后，就得到我们的答案了。
|
|
9
longSwordMan OP  1
举例：[−1, 1, −3, 4, −1, 2, 1, −5, 8]，以第一个数为终点，最大的子数列就是自己，最大和为-1，第二个数，因为 arr[1]的前一个数 arr[0]为终点的子数列是负数，所以以 arr[1]为终点，最大子数列就是自己，和就是 1，以此类推，直到最后一位。
|
Select Language