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

k长连续子段和
题意
给出一个n个数字的序列a1,a2,..an，求出所有长度大于等于k的连续子段中，子段数字和最大可以是多少。

案例
输入：3,2,[2,3,4]
返回值：9
说明：因为要选的子段的长度必须大于等于2，所以最优的选择是选择[4,-2,1]，得到的答案为3

方法一: 动态规划

定义dp数组:dp[i] 表示选取前i位中k个以上的最大连续数字和,因为是连续的且长度最少要保持k位，所以设方程为 $dp[i] = max(dp[i - 1] + a[i], pre[i] - pre[i - k])$
其中pre表示a数组的前缀和
图片说明

int dp[100001], pre[100001];
    long long solve(int n, int k, vector<int>& a) {
        // write code here
        int ans = -1000000000;
        dp[0] = 0;
        for(int i = 1; i <= n; i ++){
            pre[i] += pre[i - 1] + a[i - 1]; // 记录前缀和
            if(i < k){ // 如果i小于k则存储前k个总和
                dp[i] = dp[i - 1] + a[i - 1];
            }else{ 
                dp[i] = max(dp[i - 1] + a[i - 1], pre[i] - pre[i - k]);
                ans = max(ans, dp[i]); //更新答案
            }
        }
        return ans;
    }

时间复杂度: $O(n)$ 只需要遍历一遍a数组
空间复杂度: $O(n)$ 存储dp值与前缀和值总共复杂度为 $O(n)$

方法二: 暴力

最简单的想法就是每次遍历到第i位时从第i位逆序遍历到a数组的第一位并实时更新答案。

long long solve(int n, int k, vector<int>& a) {
        // write code here
        long long ans = -1000000000, sum = 0;
        for(int i = k - 1; i < n; i ++){ //从第k位开始遍历
            sum = 0;
            for(int j = i; j >= 0; j --){ //从后往头遍历
                sum += a[j];
                if(i - j + 1 >= k) { //如果此时所获取元素大于等于k时更新答案
                    ans = max(ans, sum);
                }
            }
        }
        return ans;
    }

时间复杂度: $O(n^2)$ 数据有点弱了如果数据强这种方*** 超时
空间复杂度: $O(1)$ 使用若干个变量