题⽬描述
输⼊⼀个整型数组，数组⾥有正数也有负数。数组中的⼀个或连续多个整数组成⼀个⼦数组。求所有⼦数组的和的最⼤值。要求时间复杂度为 O(n) .
示例1
输⼊：[1,-2,3,10,-4,7,2,-5]
返回值：18
输⼊的数组为 {1,-2,3,10,-4,7,2,-5}，和最⼤的⼦数组为 {3,10,-4,7,2}，因此输出为该⼦数组的和 18 。
思路及解答
暴⼒破解
通过两层循环枚举所有可能的子数组起点和终点，计算每个子数组的和并记录最大值。
时间复杂度：O(n²)，因为有两层嵌套循环。
空间复杂度：O(1)，只使用了常数级别的额外空间。
分治法
分治法将数组分成左右两半，分别递归求解左右半边的最大子数组和，再计算跨越中点的最大子数组和，最后合并结果。
时间复杂度：O(n log n)，由递归树深度（log n）和每层合并操作（n）决定。
空间复杂度：O(log n)，递归调用栈的深度。
动态规划
⾸先我们定义这个问题：
dp[i] 表示下标以i结尾的连续⼦数组的最⼤和，假设数组⼤⼩为 n ,那么最终求解的就是 dp[n-1] 。
下标以 i 结尾的连续⼦数组的最⼤和，怎么求呢？
要想求 dp[i] ,那我们现在假设⼀下，假设下标以i-1 结尾的连续⼦数组的最⼤和为 dp[i-1] ,数组第 i 个元素是 nums[i]，那么当前的连续⼦数组的最⼤和，要么是前⾯的加上当前的元素： dp[i-1]+nums[i]，要么是舍弃掉之前的 dp[i-1]（这个很可能是负数），取现在的 nums[i] ;
因此，状态转移⽅程为：dp[i] = max{dp[i-1]+nums[i] , nums[i]}
但是，值得注意的是， Max{dp[i-1]+nums[i],nums[i]} 求得的仅仅是以 i 下标结尾的⼦数组的最⼤和，之前计算的连续⼦数组最⼤和需要保存起来，不断的和当前计算的最⼤和⽐较，取最⼤值。
时间复杂度：O(n)
空间复杂度：O(n)
这里只用到了dp[i]和dp[i-1]，显然还可以再优化。即
时间复杂度：O(n)
空间复杂度：O(1)，只使用了两个变量。