#53_最大子序和

给定一个整数数组 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;
    }