/**
 * Find the contiguous subarray within an array (containing at least one number)
 * which has the largest sum.

 For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
 the contiguous subarray [4,-1,2,1] has the largest sum = 6.

 click to show more practice.

 More practice:
 If you have figured out the O(n) solution,
 try coding another solution using the divide and conquer approach, which is more subtle.
动态规划的经典题目，最大子串问题
 动态方程：locMAX[i] = max(locMAX[i-1] + nums[i],nums[i])
 locMAX表示局部最大的子串，必须要包含现在的数nums[i]，每遍历一个数，状态都要更新
 还要设置一个全局最大数，gloMAX = max(locMAX[i],gloMAX)，意思是：
 如果最后结果包括局部的子串，那么全局就是这个局部，如果不包含这个局部，那么全局还是前边的全局
 */
public class Q53MaximumSubarray {
    public static void main(String[] args) {
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }
    public static int maxSubArray(int[] nums) {
        int glo = nums[0];
        int loc = nums[0];
        for (int i = 1; i < nums.length; i++) {
            loc = Math.max(loc + nums[i],nums[i]);
            glo = Math.max(glo,loc);
        }
        return glo;
    }
}