题解 | #k长连续子段和#

题意整理

给定由n个数字组成的一个序列。
求所有长度大于等于k的连续子段中，子段和的最大值。

方法一（枚举k长子段和）

1.解题思路

首先定义结果变量，用于记录最终结果。
固定子段和开始处索引，枚举所有长度的子段，并记录子段和。如果长度大于等于k，则与res比较，并记录最大值。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int k, int[] a) {
        //定义结果变量
        long res=Long.MIN_VALUE;

        for(int i=0;i<n;i++){
            //记录以i开始的所有子段和
            long sum=0;
            for(int j=i;j<n;j++){
                sum+=a[j];
                //如果子段长度大于等于k，则在其中取最大值
                if(j-i+1>=k){
                    res=Math.max(res,sum);
                }
            }
        }       
        return res;
    }
}

3.复杂度分析

时间复杂度：总共两层循环，最多执行 $n^2$ 次，所以时间复杂度是 $O(n^2)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O(1)$ 。

方法二（动态规划）

1.解题思路

初始化前缀数组presum，用于统计前缀和。
定义dp数组， $dp[i]$ 表示以i-1下标结尾，长度至少为k的最大字段和。
初始化k-1下标处结尾的子段对应dp值。
从k-1下标处结尾对应状态开始往后推导，后面的状态要么是前一个下标的状态最大值加上当前数字，要么是当前下标结尾处往前数k个数对应的子段和。

动图展示：
图片说明

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int k, int[] a) {
        //统计前缀和
        long[] presum=new long[n+1];
        for(int i=0;i<n;i++){
            presum[i+1]=presum[i]+a[i];
        }

        //初始化dp数组,dp[i]表示以i-1下标结尾，长度至少为k的最大子段和
        long[] dp=new long[n+1];
        //给以k-1下标处结尾的子段对应dp赋初值，其他状态都是由此状态依次推导出来
        dp[k]=presum[k]-presum[0];
        long res=dp[k];

        //当子段以i-1结尾时，最大子段和要么是以i-1结尾往前数k个数组成的子段和，要么是i-2结尾的最大值加上当前数字
        for(int i=k+1;i<=n;i++){
            dp[i]=Math.max(dp[i-1]+a[i-1],presum[i]-presum[i-k]);
            res=Math.max(res,dp[i]);
        }

        return res;
    }
}

3.复杂度分析

时间复杂度：所有的循环都是线性的，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为n+1的presum数组和dp数组，所以空间复杂度是 $O(n)$ 。