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.

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

Have you met this question in a real interview?  

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

Code(Language:C++)

class Solution {
public:
    /**
     * @param nums: an array of integer
     * @param k: an integer
     * @return: the largest sum
     */
    int maxSubarray4(vector<int> &nums, int k) {
        // write your code here
        const int size = nums.size();
        if(size < k){
            return 0; 
        }
        vector<int> prefixSum(size + 1, 0);
        vector<int> prefixSumMin(size + 1, 0);
        for(int i = 0; i < size; i++){
            prefixSum[i + 1] = prefixSum[i] + nums[i]; 
            prefixSumMin[i + 1] = min(prefixSum[i + 1], prefixSumMin[i]); 
        }
        int res = INT_MIN; 
        for(int i = k - 1; i < size; i++){
            res = max(res, prefixSum[i + 1] - prefixSumMin[i - k + 1]);
        }
        return res; 
    }
};