这是一个创建于 2009 天前的主题，其中的信息可能已经有所发展或是发生改变。
在上一个帖子主要和大家分享了刷 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