Lintcode 620. Maximum Subarray IV

Given an integer arrays, find a contiguous subarray which has the largest sum and length should be greater or equal to given length k.
Return the largest sum, return 0 if there are fewer than k elements in the array.

Example

Example 1:

Input:
[-2,2,-3,4,-1,2,1,-5,3]
5
Output:
5
Explanation:
[2,-3,4,-1,2,1]
sum=5

Example 2:

Input:
[5,-10,4]
2
Output:
-1

Notice

1. Ensure that the result is an integer type.
2. k > 0

Code (Java):

public class Solution {
    /**
     * @param nums: an array of integer
     * @param k: an integer
     * @return: the largest sum
     */
    public int maxSubarray4(int[] nums, int k) {
        // write your code here
        if (nums == null || nums.length < k) {
            return 0;
        }
        
        int[] minPresum = new int[nums.length + 1];
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        
        for (int i = 1; i <= nums.length; i++) {
            sum += nums[i - 1];
            minPresum[i] = Math.min(minPresum[i - 1], sum);
            
            if (i >= k) {
                maxSum = Math.max(maxSum, sum - minPresum[i - k]);
            }
        }
        
        return maxSum;
    }
}