这是leetcode面试刷题一题多解系列的第4篇，求最大子数组之和，练习下简单的动态规划和分治算法。
题目
今天跟大家一起看一道经典的动态规划问题，了解下动态规划的核心思想，确定状态转移方程，最大子数组和。
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
来源：力扣（LeetCode）
链接：leetcode.cn/problems/ma…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解1---贪心算法
贪心算法的核心是每次选择当前看起来最优的解，希望最终得到全局最优的解。贪心算法通常能解决一些特殊问题，例如最短路径问题、背包问题、最小生成树等，下面这道题比较简单，主要是让大家感受下贪心的基本思想。
var maxSubArray = function(nums) {
// 定义初始值为数组的第一个元素
let ans = nums[0];
// 定义一个变量sum，用于存储当前连续子数组的和，初始值为0
let sum = 0;
for(const num of nums) {
// 如果当前连续子数组的和大于0，则将当前元素加到连续子数组中
if(sum > 0) {
sum += num;
}
// 否则，更新连续子数组和为当前元素
else {
sum = num;
}
// 更新最大子数组和
ans = Math.max(ans, sum);
}
// 返回最大子数组和
return ans;
};
在这个算法中，每次循环时，我们考虑的是当前连续子数组的和是否大于0。如果是，则将当前元素加入到连续子数组中，以期望得到更大的和；否则，重新将当前元素作为新的连续子数组的第一个元素，继续向后遍历。这种做法可能不是最优解，但通过不断地贪心选择，最终可以得到全局最优解，即整个数组中连续子数组的最大和。 我们只需要遍历一遍数组即可求得答案，所以时间复杂度是 O(N), 只需要常数空间，与输入数组长度无关，所以空间复杂度 O(1)。
题解2---动态规划
动态规划是一种解决多阶段决策过程中的最优化问题的算法思想，其核心思想是将问题分解为若干个子问题，并存储已经求解过的子问题的解，以便在求解当前问题时能够复用这些子问题的解，从而避免重复计算。
动态规划的核心是找出转移方程，转移方程是指根据子问题之间的关系，定义子问题之间的求解方程，这道题的转移方程是：f(i)=max{f(i−1)+nums[i],nums[i]}，其中f(i) 代表以第i个数结尾的「连续子数组的最大和」,利用这个状态方程很容易就能编写出下面的代码。
var maxSubArray = function(nums) {
// pre为当前位置之前的子数组的最大和
// maxAns为找到的最大子数组的和
let pre = 0, maxAns = nums[0];
nums.forEach((x) => {
// 这个算法的核心状态转移方程
pre = Math.max(pre + x, x);
// 和之前的最大值比较，求出新的最大值
maxAns = Math.max(maxAns, pre);
});
return maxAns;
};
我们只需要遍历一遍数组即可求得答案，所以时间复杂度是 O(N), 只需要常数空间，所以空间复杂度 O(1)。