描述
給定一個(gè)整數(shù)數(shù)組抄瓦，找到長(zhǎng)度大于或等于 k 的連續(xù)子序列使它們的和最大盯串，返回這個(gè)最大的和，如果數(shù)組中少于k個(gè)元素則返回 0
注意事項(xiàng)
確保返回結(jié)果為整型
樣例
給定一個(gè)數(shù)組為 [-2,2,-3,4,-1,2,1,-5,3]柴梆，k = 5胀瞪，連續(xù)的子序列為 [2,-3,4,-1,2,1] 時(shí)有最大和 sum = 5
代碼
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;
}
// result的初始化，前 i 個(gè)數(shù)之和
int result = 0;
for (int i = 0; i < k; ++i) {
result += nums[i];
}
int[] sum = new int[n + 1];
sum[0] = 0;
int min_prefix = 0;
for (int i = 1; i <= n; ++i) {
// sum[i]代表前i - 1個(gè)數(shù)之和
sum[i] = sum[i - 1] + nums[i - 1];
if (i >= k && sum[i] - min_prefix > result) {
result = Math.max(result, sum[i] - min_prefix);
}
// i 每增大1脚祟，min_prefix也要和新的sum[i - k + 1]比較是否出現(xiàn)更小的min_prefix
// min_prefix的選擇范圍始終和當(dāng)前i之間隔著k個(gè)數(shù)
if (i >= k) {
min_prefix = Math.min(min_prefix, sum[i - k + 1]);
}
}
return result;
}
}
