# Maximum Subarray IV

(Largest sum subarray with at-least k numbers)

### Description

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

Ensure that the result is an integer type.

Example

Given the array[-2,2,-3,4,-1,2,1,-5,3]and k =5, the contiguous subarray[2,-3,4,-1,2,1]has the largest sum =5.

## Analysis

maxSum的基准是前k个元素之和；前缀和的最小值minPrefix在取用的时候需要比较的是sum[i - k] 也就保证了maxSum的取值的区间长度至少是k (sum[i] - sum[i - k], i - (i - k) = k)。

## Solution

(455 ms beats 82.80%)

public class Solution {
/**
* @param nums an array of integers
* @param k an integer
* @return the largest sum
*/
public int maxSubarray4(int[] nums, int k) {
int n = nums.length;
if (n < k) return 0;

int maxSum = 0;
for (int i = 0; i < k; i++){
maxSum += nums[i];
}

int[] sum = new int[n + 1];
sum[0] = 0;

int minPrefix = 0;
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + nums[i - 1];
if (i >= k) {
minPrefix = Math.min(minPrefix, sum[i - k]);
maxSum = Math.max(maxSum, sum[i] - minPrefix);
}
}
return maxSum;
}
}

Another one

public class Solution {
/**
* @param nums an array of integers
* @param k an integer
* @return the largest sum
*/
public int maxSubarray4(int[] nums, int k) {
int n = nums.length;
if (n < k)
return 0;

int maxSum = 0;
for (int i = 0; i < k; ++i)
maxSum += nums[i];

int[] sum = new int[n + 1];
sum[0] = 0;

int min_prefix = 0;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + nums[i - 1];
if (i >= k) {
maxSum = Math.max(maxSum, sum[i] - min_prefix);
min_prefix = Math.min(min_prefix, sum[i - k + 1]);
}
}
return maxSum;
}
}

## Reference

[Maximum Subarray IV](https://gpp676.wordpress.com/2017/10/13/maximum-subarray-iv/