打开率不足1.5%
编辑日期: 2024-11-28 文章阅读: 次
你好，我是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)
定义状态变量，进而准确的确定出状态转义方程，说起来容易，做起来需要日复一日的去思考和练习。
希望你能从我这篇文章中，获取一些启发，为你开启动态规划思想的大门。祝愿你跳槽成功，薪资翻倍。
