Maximum Subarray IV

Problem Description: http://lintcode.com/en/problem/maximum-subarray-iv/

public int maxSubarray4(int[] nums, int k) {
    // Write your code here
    if(k > nums.length) return 0;
    int[] sum = new int[nums.length + 1];
    int max = Integer.MIN_VALUE, minSum = 0;
    for(int i = 1; i < sum.length; i++){
        sum[i] = sum[i - 1] + nums[i - 1];
        if(i >= k){
            minSum = Math.min(minSum, sum[i - k]);
            max = Math.max(max, sum[i] - minSum);
        }
    }

    return max;
}

public int maxSubarray4(int[] nums, int k) {
    // Write your code here
    if(k > nums.length) return 0;
    int[] sum = new int[nums.length + 1];
    int max = Integer.MIN_VALUE, minSum = 0;
    for(int i = 1; i < sum.length; i++){
        sum[i] = sum[i - 1] + nums[i - 1];
        if(i >= k){
            max = Math.max(max, sum[i] - minSum);
            minSum = Math.min(minSum, sum[i - k + 1]);
        }
    }

    return max;
}

For 0 < i < j < length, the sum of subarray nums[ i ] + ... + nums[ j ] is equal to sum[ j ] - sum[ i - 1 ].

There are two ways to use minSum and max above, pay attention to the order and index of them