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

思路：

题目的主要信息：

给出一个序列a，从中选出长度大于等于k的连续子序列，使子序列和最大
k一定不大于序列长度
连续子段指的是序列中一段连续的数字

方法一：暴力解法
具体做法：
首先长度的种类包含k到n这些长度，我们要遍历所有的长度选项。
然后，对于每一个选项，遍历数组找到每一个可以起点的元素，向后相加长度那么多个单位即可得到一次的结果，我们比较每次的结果，取最大值即可。

class Solution {
public:
    long long solve(int n, int k, vector<int>& a) {
        long long res = LONG_LONG_MIN;
        for(int i = k; i <= n; i++){ //遍历k及k以上的所有长度选项
            for(int j = 0; j + i <= n; j++){ //起点位置不定
                long long temp = 0;
                for(int x = j; x < j + i; x++) //长度为i
                    temp += a[x]; //相加
                res = max(res, temp);
            }
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O((n-k)*n^2)$ ，里面两层都是 $O(n)$ ，最外层只从 $k$ 到了 $n$
空间复杂度： $O(1)$ ，常数空间

方法二：动态规划
具体做法：
我们使用数组sum保存前缀和，即 $sum[i]$ 表示前 $i$ 个元素的和。那么 $sum[i] - sum[i - k]$ 就表示中间连续k个数字的和。
我们用dp数组辅助动规划，其中 $dp[i]$ 表示以 $i$ 结尾的最大子序列和，遍历 $k$ 及以后的 $dp[i]$ ，它可以等于 $dp[i - 1] + a[i]$ （继续延申长度），也可以等于新的 $k$ 个长度的子序列和 $sum[i] - sum[i - k]$ ，取最大值即可。
图片说明

class Solution {
public:
    long long solve(int n, int k, vector<int>& a) {
        long long res = LONG_LONG_MIN;
        vector<long long> sum(n, 0);
        sum[0] = a[0];
        for(int i = 1; i < n; i++)
            sum[i] = sum[i - 1] + a[i]; //前缀和
        vector<long long> dp = sum; //dp[i]表示以i结尾的最大子序列和，i小于k不用管
        for(int i = k; i < n; i++)
            dp[i] = max(dp[i - 1] + a[i], sum[i] - sum[i - k]);
        for(int i = k - 1; i < n; i++)
            res = max(res, dp[i]); //找到最大值
        return res;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，三次都是单层循环
空间复杂度： $O(n)$ ，两个辅助数组sum和dp最大长度为 $n$ ，res属于返回函数必要空间