算法-求最大子序列和

题目描述：

转载来自于Rui用户解题思路 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

方法：

实际上我曾经疑惑过怎么在变量少构建而且有用动态规划的方式去完成此题： 下面的代码很好的解决了这个矛盾：

代码1：
class Solution {
public int maxSubArray(int[] nums) {
    int res = nums[0];
    int sum = 0;
    for (int num : nums) {
        if (sum > 0)
            sum += num;
        else
            sum = num;
        res = Math.max(res, sum);
    }
    return res;
}
}

分析：

实际上很有意思的事情，这和股票那几道题目十分相似： 核心就是动态规划；在发现前面的求和总数为负数的时候重新选择求和索引开头用了一下语句

       if (sum > 0)
            sum += num;
        else
            sum = num;

不可谓不精妙，不需要多定义一个求和起点（毕竟不要求返回最终数组的首尾元素索引），用sum = num来表示这个过程更加精彩。

原理：

设sum<=0，那么后面的子序列肯定不包含目前的子序列，所以令sum = num；如果sum > 0对于后面的子序列是有好处的。res = Math.max(res, sum)保证可以找到最大的子序和。