620. 最大子序列的和IV

描述

给定一个整数数组，找到长度大于或等于 k 的连续子序列使它们的和最大，返回这个最大的和，如果数组中少于k个元素则返回 0

注意事项

确保返回结果为整型

样例

给定一个数组为 [-2,2,-3,4,-1,2,1,-5,3]，k = 5，连续的子序列为 [2,-3,4,-1,2,1] 时有最大和 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 个数之和
        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个数之和
            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]比较是否出现更小的min_prefix
            // min_prefix的选择范围始终和当前i之间隔着k个数
            if (i >= k) {
                min_prefix = Math.min(min_prefix, sum[i - k + 1]);
            }
        }
        return result;
    }
}