# 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 length`k`.\
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

这一题跟之前的Maximum subarray sum有一些区别，Kadane Algorithm不是能很好的应用这这里。

在于求解区间和时要求了区间的长度大于等于k。

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

## Solution

(455 ms beats 82.80%)

```java
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

```java
public class Solution {
    /**
     * @param nums an array of integers
     * @param k an integer
     * @return the largest sum
     */
    public int maxSubarray4(int[] nums, int k) {
        // Write your code here
        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/](https://gpp676.wordpress.com/2017/10/13/maximum-subarray-iv/\)/)

GeeksforGeeks: <https://www.geeksforgeeks.org/largest-sum-subarray-least-k-numbers/>