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.
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;
}
}