Maximum Subarray

Subarray类型基础题，此题最简单的方式就是通过动态规划逐个往前递推，看当前数是自己单独比较大还是和之前的积累和加在一起比较大，如果是单独比较大则把积累和改为当前值，最后这个过程里面的最大值就是最终结果

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tmp, result = 0, -sys.maxint
        for num in nums:
            tmp = max(tmp + num, num)
            result = max(result, tmp)
        return result

另外在算法导论里面介绍过一种利用分治法解这道题的方法，但是这种方法比较复杂，暂时没有研究

Java版本

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = 0;
        int result = Integer.MIN_VALUE;
        for (int num : nums) {
            cur = Math.max(num, cur + num);
            result = Math.max(cur, result);
        }
        return result;
    }
}