大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天看到一位在国企工作了两年半，985硕士毕业的同学被裁了。评论区不少同学表示震惊，纷纷表示不是听说国企很稳定吗？咋也裁人。也有不少相同经历的同学说已经见怪不怪了，其实很多套着国企外衣的公司，内部管理制度和私企没啥区别，甚至比私企更离谱。而且国企末位淘汰现在也是有强制名额了。
被裁员是职场常见现象，尤其是在不确定的经济环境下，保持积极的心态和灵活应对变化的能力非常重要。
最近虎哥利用业余时间在B站讲算法，id「华南溜达虎」，我已经把算法面试高频题目列表blind75中的题目讲了一遍，力扣hot100也快讲完了，一个视频五分钟左右，利用空闲时间就把算法学会了，对跳槽找工作升职加薪甚至对考研都有帮助，感兴趣的同学可以 点击底部的「查看全文」 去学习一下。很多看过虎哥视频的同学都反馈讲的由浅及深，清晰明了，下面是一小部分评论截图。
言归正传，今天我们来分享一道比亚迪的面试原题「最大子数组和」。
题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
举个例子：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
思路解析
本题可以通过暴力循环来解，但是时间复杂度太大，暴力解法也不是出题的意图。我们还可以通过动态规划来解此题，动态规划的关键就是推导状态转移公式，下面我们来一步步推导此题的状态转移公式。
定义cur_max[i]为以nums中第i个元素结尾，子数组和的最大值，其中0 <= i < nums.size。在推导cur_max[i]的过程中会枚举以nums中任意元素结尾，和最大的子数组。最终我们从cur_max[i]中选择最大的一个即是最终要返回的结果。
考虑数组元素全部都是大于等于 0的场景：
在这种场景下，因为元素都是正数，不难看出cur_max[i] = cur_max[i-1] + nums[i]。
考虑数组元素包含负数的场景：
由于cur_max[0] = -1，负数加上一个数会导致和变得更小。那么cur_max[1] != cur_max[0] + nums[1]，正确的结果为cur_max[1] = nums[1]。进一步优化转移公式为cur_max[i] = max{cur_max[i-1] + nums[i], nums[i]}。
实现优化
上面的状态转移公式如果用代码来实现需要用到一个跟nums长度一致的数组cur_max。因为题目要求找到子数组最大的和，我们不需要把每个子数组的状态都保存下来，只保存上一个状态就可以。使用一个整型变量max_res来保存全局的最大和。
下面我们给出c++和python的两种代码实现。
C++代码
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max_res = nums[0];
int cur_max = nums[0];
for(int i = 1; i < nums.size(); ++i){
//状态转移公式
cur_max = max(cur_max + nums[i], nums[i]);
max_res = max(max_res, cur_max);
}
return max_res;
}
};
python代码
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxRes = nums[0]
curMax = nums[0]
for i in range(1, len(nums)):
#状态转移公式
curMax = max(curMax + nums[i], nums[i])
maxRes = max(maxRes, curMax)
return maxRes
复杂度分析
时间复杂度： 由于只需要遍历一遍nums，故时间复杂度为O(n)，其中n为nums的长度。
空间复杂度： 整个过程只使用了两个整型变量，所以空间复杂度为O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
