给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答参考以下作者,真的是太强了吧,看答案都想了好久才理清
作者：guanpengchn
链接：https://leetcode-cn.com/problems/two-sum/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 思路
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
// created by fivezm on 20,7 2019
public static int maxSubArray(int[] nums) {
int ans = nums[0]; // 假设 数组的第一个元素时最大的,是答案
int sum = 0; // sum 为子序列相加的和
for (int num : nums) {
if (sum > 0) { // 如果子序列大于0,则证明对答案有正增长,将它们累加起来
sum += num;
} else { // 如果子序列小于等于0,则证明对答案有负增长或无增长,这是要舍弃之前的sum,重新将这一个num元素设置为子序列的第一个
sum = num;
}
ans = Math.max(ans, sum); // ans有可能是最大的,,累加得到的sum也有可能是最大的,那么要判断一下哪一个最大,赋值给ans变量,因为sum变量是一直都在变
}
return ans;
}
