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

题目描述
给出一个n个数字的序列a1,a2,…an，你想知道所有长度大于等于k的连续子段中，子段数字和最大可以是多少。

连续子段指的是序列中一段连续的数字。子段数字和指的是子段中所有数字相加的和。

方法一：暴力求解

求解思路
对于本题目的求解，我们记录连续子段的起始位置和子段的长度，然后从n个序列开始依次遍历，维护一个最大值即可，按照上述的思想，即可得到本问题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public long solve (int n, int k, int[] a)
    {
        long myres=Long.MIN_VALUE; // 存储结果
        for(int i=0;i<n;i++)
        {
            long sum=0; // 一个临时的最大值，和myres进行比较，最终返回结果
            for(int j=i;j<n;j++)
            {
                sum+=a[j];
                if(j-i+1>=k)
                {
                    myres=Math.max(myres,sum); // 更新最大值
                }
            }
        }
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：两层循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：常数级空间，因此空间复杂度为 $O(1)$

方法二：优化思想求解

求解思路
对于本问题我们还可以采用动态规划的思想进行求解，dp[i]表示以i-1为结尾，长度大于等于k的连续子段的和。对于状态转移方程下图展示。

图片说明

解题代码

import java.util.*;
public class Solution {
    public long solve (int n, int k, int[] a)
    {
        long[] pre=new long[n+1]; // 临时变量
        for(int i=0;i<n;i++)
        {
            pre[i+1]=pre[i]+a[i]; // 跟新临时变量
        }
        long[] mydp=new long[n+1]; // 声明dp数组
        mydp[k]=pre[k]-pre[0]; // 赋值
        long myres=mydp[k]; // 声明结果
        for(int i=k+1;i<=n;i++)
        {
            mydp[i]=Math.max(mydp[i-1]+a[i-1],pre[i]-pre[i-k]); // 状态转移
            myres=Math.max(myres,mydp[i]);
        }
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用mydp[n],因此空间复杂度为 $O(N)$