题目
来源：0053.最大子数组和
给你一个整数数组 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 <= 10^5-104 <= nums[i] <= 10^4
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
分析
我们从最简单的情况看起，对于只有一个元素的数组，其具有最大和的连续子数组就是这个元素构成的数组，最大和就是这个元素的值。
我们用 max 表示所求的最大和，用 sum 表示当前子数组的和。
对于有两个元素的数组，我们这样来看：
由第一个元素构成的子数组，最大和我们已经知道了（max = sum = nums[0]），就是这个元素的值；那么将第二个元素放入这个子数组中之后呢，要计算此时的最大和，就有两种情况。
如果第二个元素为正，显然当前子数组的和 sum + nums[1] > sum，若 sum > 0，则具有最大和的连续子数组为 [nums[0], nums[1]]，最大和为 sum + nums[1]；
若 sum <= 0，则具有最大和的连续子数组为 [nums[1]]，最大和为 max = nums[1];
如果第二个元素为负，当前子数组的和 sum + nums[i] < nums[1]，那么具有最大和的子数组为 [nums[0]]，最大和为 sum。
综合这两种情况，我们可以看出，无论第二个元素为正或负，当前子数组的最大和为 sum = Math.max(sum + nums[1], nums[1])，所求的最大和为 max = Math.max(sum, max)。
这是长度为 2 的数组的情况，扩展到长度为 n 的数组，他的前 2 个元素构成的子数组，我们可以通过上述方法得到结果；对于他的位置为 [0, i] 的元素构成的子数组，sum = Math.max(sum + nums[i], nums[i]), max = Math.max(sum ,max)。
这种方法用了 动态规划 的思想，假设我们用 dp[i] 表示由位置 [0, i] 的元素构成的数组中，具有最大和的连续子数组，他的最大和。那么
sum = Math.max(sum + nums[i], nums[i]);
dp[i] = Math.max(sum, dp[i - 1]);
解答
由于我们求解的就是这个长度为 n 的数组所满足的 dp[n - 1]，遍历完后返回 dp[n - 1] 的值即可，无需再创建一个长度为 n 的 dp 数组。
public class Solution {
public int maxSubArray(int[] nums) {
int max = nums[0];
int sum = 0;
for (int num : nums) {
sum = Math.max(sum + num, num);
max = Math.max(max, sum);
}
return max;
}
}
至于题目所说的 分治法，我看了一眼题解，感觉很复杂，代码也比较长，就没有去研究。