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

这一题跟之前的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%)

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) {
        // 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/

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