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

题目：
给出一个n个数字的序列，求所有长度大于等于k的连续子段中，子段数字和最大可以是多少。
连续子段指的是序列中一段连续的数字。子段数字和指的是子段中所有数字相加的和。
关键：求长度大于等于k的最大连续子段数字和
方法一：双指针
左指针和右指针都置于起点，序列中的每个数字都可以作为子段的起点，当第一个数字作为起点，右指针向右移动，保存子段和直到子段长度大于等于k时，开始维护子段和的最大值，当右指针指向末尾时，寻找以第一个数字作为起点的子段结束，左指针右移，重置右指针和sum，开始寻找以下一个数字作为起点的子段，重复以上步骤，直到遍历完整个序列
图片说明

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) {
        // write code here
        int l=0,r=0;
        long sum=0;
        long res=Integer.MIN_VALUE;
        //每个数字都可以作为起点
        while(l<n&&r<n){
            //计算子段数字和
            sum+=a[r];
            //当长度大于等于k时，更新最大值
            if(r-l+1>=k)
                res=Math.max(res,sum);
            r++;
            //下一个数字作为起点，重置子段和为0
            if(r==n){l++;r=l;sum=0;}
        }return res;
    }
}

复杂度：
时间复杂度：一层循环，线性时间复杂度 $O(n)$
空间复杂度：只使用了几个额外的辅助变量，额外空间为常数级， $O(1)$
方法二：动态规划
$dp[i]$ 表示以 $a[i+k-1]$ 结尾的最大子序列和

子段长度最小为k,因此先计算前k个数字的和初始化 $dp[0]$
状态转移方程：

图片说明

找出 $max(dp[i])$ 即为最大子段和

图片说明

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) {
        // write code here
        long[]dp=new long[n-k+1];//dp[i]表示以a[i+k-1]结尾的子段和最大值
        long sum=0;
        for(int i=0;i<k;i++)sum+=a[i];//计算以a[k-1]结尾的子段和,初始化dp[0]
        dp[0]=sum;
        long res=dp[0];
        for(int i=1;i<dp.length;i++){
            //长度大于k的第一个子段和需要特殊处理,在是否减去a[0]之间取最大值
            if(i==1)dp[i]=Math.max(dp[i-1]+a[i+k-1],dp[i-1]+a[i+k-1]-a[0]);
            else//如果子段长度最小值是1,则在本身与本身加上dp[i-1]之间取最大值,否则为上一个数字结尾的最大子段和加上本身
                dp[i]=(k==1)?Math.max(a[i+k-1],dp[i-1]+a[i+k-1]):dp[i-1]+a[i+k-1];
             res=Math.max(res,dp[i]);//维护最大值
        }
        return res;
    }
}

复杂度：
时间复杂度：最多遍历序列一次，时间复杂度为 $O(n)$
空间复杂度： $dp$ 数组大小不超过n，空间复杂度为 $O(n)$