给你一个整数数组 nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
-
1 <= nums.length <= 105 -
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 \$O(n)\$ 的解法，尝试使用更为精妙的 分治法 求解。
使用动态规划，在“当前元素”与“当前元素加之前数组的和”之间，取最大值作为动态规划的结果，向前推进。在所有动态结果中，取最大值即可。
\$f(x)\$ 表示从 0 到第 x 个元素的最大子数组和，如果第 x-1 个元素的最大子数组之和大于 0，则可以继续向上“盖楼”；当小于等于 0 时，可以抛弃前面的元素从新开始。则递推公式是： \$f(x)=max(f(x-1),0)+a[x]\$。这个做法也叫做 Kadane 算法。
|
Note
|
另有更精妙的分治解法和前缀和解法，抽空再尝试。 |
- 一刷
-
link:{sourcedir}/_0053_MaximumSubarray.java[role=include] - 二刷
-
link:{sourcedir}/_0053_MaximumSubarray_2.java[role=include] - 三刷
-
link:{sourcedir}/_0053_MaximumSubarray_3.java[role=include] - 四刷
-
link:{sourcedir}/_0053_MaximumSubarray_4.java[role=include] - 五刷
-
link:{sourcedir}/_0053_MaximumSubarray_5.java[role=include]