LeetCode53.最大子数组和

要求最大连续子数组的和，可以这样考虑，比如现在我想求下标 i~j,i<j 这一范围内子数组的和，那么我可以分别先求出 0~i-1 范围和 0~j 范围两个子数组的和，可得Sum[i~j]=Sum[0~j]-Sum[0~i-1] ，这就是本题解法的核心思想。

解法详细描述：先从下标0开始，遍历 nums 数组，求出到当前下标位置的子数组和，得到 sumUntilPos 数组，再遍历  sumUntilPos  数组，从当前位置往前找该数组中值最小的元素，然后用当前位置的元素减去该值最小元素，即可获以当前位置为终点，最大的子数组之和是多少。最后选取其中求出的最大的子数组和返回。

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int maxSum = -0xffff;
        int minSum = 0;
        int n = nums.length;
        int[] sumUtilPos = new int[n];
        for(int i=0;i<n;i++){
            sum += nums[i];
            sumUtilPos[i] = sum;
        }
        for(int j=0;j<n;j++){
            if(sumUtilPos[j]-minSum > maxSum)
                maxSum = sumUtilPos[j]-minSum;
            if(minSum > sumUtilPos[j])
                minSum = sumUtilPos[j];
        }
        return maxSum;
    }
}