你好，我是zhenguo

这是我的第506篇原创

打开率不足1.5%

关注我的读者近6万，但是公众号打开率日益下降，最近几篇的阅读打开率已经不足1.5%，这令我有些沮丧，但是作为一名写作近5年的创作者，我不会因此而停下前进的脚步，我还会一如既往，持续为你创造真正有用的技术干货。
提升技术靠的是日积月累的思考和训练，没有所谓的灵丹妙药，也没有一个又一个所谓的神器。学技术就像过日子，平平淡淡才是真。

面试第一关一般是算法面试题

有段时间没更新算法相关的文章了，现在三四月份，关注我的读者应该会有想换工作的，要想涨薪，跳槽自然是最捷径的方法之一，所以跳槽太正常了。技术面试往往第一关通通都是算法题，不管是前后端，算法和数据分析，皆如此。
算法面试题中最不容易想出来的就是动态规划的题目，尤其是如果你没有系统练习或者从来没有练习的话，基本上是不会想出更好时间复杂度的求解方法的。因为没有系统培养算法设计技术的程序员，所拥有的的思维基本是枚举、穷举这种逻辑表达，遗憾的是，这种思维往往时间复杂度高，不是面试官想看到的求解。

子数组和的最大值

今天我以一道leetcode上easy级别的题目，来解释如何运用动态规划构思和求解题目。
别看这是easy的题目，如果你没有仔细思考和练习，也很容易做不出这道题。
题目是这样：
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

nums的子数组长度可能是1~len(nums)任意值，比如如果长度为3，那么可能为：
[-2,1,-3]

[1,-3,4]

[-3,4,-1]

[4,-1,2]

[-1,2,1]

[2,1,-5]

[1,-5,4]

每一种长度，对应的情况趋向于len(nums)，因此如果枚举所有情况子区间，时间复杂度为O(n^2)

如何构思动态规划？

而动态规划却能做到O(n)时间复杂度，获得更好的时间性能，但往往使用动态规划会付出一定代价，因为你要以付出空间成本为代价。空间是用来记忆状态和取值的，这里马上引出一个问题：
如何定义状态，换言之，隐含的这个空间变量它的定义是什么？这是所有动态规划都需要定义的，也是最重要的状态变量。
如何设计或抽离出状态变量更多的需要天长日久的训练和思考，即便有所谓的设计技巧，也很难完全复现成文字展现出来。
不过，我还是想说一下我自己平时常用到的方法，一般需要基于题目反复尝试几种定义，找到最贴题目的定义，定义准确的状态变量，让你更容易写出正确的状态转移方程。
比如连续子区间最大和这道题目，这里面最重要的一个特征是区间要保证连续，换言之，必须要定义类似这种状态变量cur_max，它的含义：包括当前迭代到的元素nums[j]的区间最大和，基于此状态变量，我们做如下推演：
当j=0时，也就是包括第一个元素的区间和，此时只有它一个元素，显然cur_max等于nums[j]；
当j=1时，包括第二个元素的区间最大和cur_max应该等于几呢？发现在有了这个状态变量后，马上能做出这个推理：
  • 如果上一个状态的cur_max是大于0的，那么包括当前元素nums[j]的区间最大和等于：cur_max+nums[j]，这个是一定成立的，这点你能想明白吗？可以仔细想一想是不是可以做出这种推理
  • 换言之，如果上一个状态的cur_max是小于0的，那么包括当前元素nums[j]的最大和只能等于nums[j]，这点也不难推理
以此类推，我们遍历完成后，可以求出每一个状态下cur_max的取值，只需要找到最大的cur_max就可以了。
一般地，我们会一边遍历，一边使用另一个变量，比如pre_max记忆住过往最大值，这样遍历完成后，就能得到最大值，而不用再重新对所有状态下得到的cur_max系列值求最大。这样还能节省一定的空间。

代码

有了上面的思考，我们就会很容易写出下面的代码，并且不会随着时间而忘掉。有些读者跟我反馈过，LeetCode题目刷过容易忘掉解法，其实不是忘了，而是没有经过深入的思考和总结。
class Solution:

    def maxSubArray(self, nums: List[int]) -> int:

if
 len(nums) == 0:

return
 None

        pre_max, cur_max = -
float
(
'inf'
), nums[0]

for
 j 
in
 range(1, len(nums)):

            pre_max = max(pre_max, cur_max)


if
 cur_max < 0:

                cur_max = nums[j]

else
:

                cur_max += nums[j]


return
 max(pre_max, cur_max)

定义状态变量，进而准确的确定出状态转义方程，说起来容易，做起来需要日复一日的去思考和练习。
希望你能从我这篇文章中，获取一些启发，为你开启动态规划思想的大门。祝愿你跳槽成功，薪资翻倍。

宣传我的课程

课程视频制作初衷：根据我过往7年多工作经历，5年多自媒体技术写作经验，以及期间与粉丝们的各种各样的交流，最终我决定打造这个系列课程，全由我一人完成，保证质量。真正帮助那些想从零完成就业的小伙伴们。路在何方，路在脚下。
课程总览：全是Python视频系列课程，包括多门课，帮助你从零到就业。不止一门课，目前已有从零学Python精品120课，正在更新从零学Python网络爬虫，从零学Python数据分析等。每课长度在2分钟~20分钟不等。
课程服务：课程提供电脑和手机双端学习平台，除了多门课精品视频外，还有配套讲义，完整源码文件。最重要的，会设有班级答疑群，解答疑问。
目前已有23个章节的课程大纲（包括从零学Python编程，从零学爬虫，从零学数据分析），鉴于篇幅有限，我就不一一放到这里了，感兴趣的点击下图二维码去了解：
继续阅读
阅读原文
关键词
动态规划
数组
算法
子数组
时间复杂度