k长连续子段和

最优解法

解法1：动态规划
用表示以位置为结尾，长度大于等于的所有子段中最大的子段和。那么考虑转移：
以位置为结尾的大于等于k的子段分为两种：

1. 长度刚好等于，这种情况下最大子段和等于这个数字的和
2. 长度大于，这种情况下最大子段和等于

需要前缀和数组和dp数组辅助求解，空间复杂度，时间复杂度

long long dp[100005];
long long sum[100005];
long long solve(int n, int k, vector<int> &a){
    assert(a.size() == n);
    memset(dp, 0, sizeof dp);
    sum[0] = a[0];
    for(int i = 1; i < n; ++i) sum[i] = sum[i-1] + a[i];
    dp[k-1] = sum[k-1];
    long long ans = dp[k-1];
    for(int i = k; i < n; ++i){
        dp[i] = sum[i]-sum[i-k];
        dp[i] = max(dp[i-1]+a[i], dp[i]);
        ans = max(ans, dp[i]);
    }return ans;
}

解法2：前缀和
求出前缀和数组，长度大于等于就要求选择的两个前缀和距离必须大于等于。
那么枚举右端点,子段和等于，要小于等于。那么另一个指针维护一下的最小值即可。
需要前缀和数组求解，空间复杂度，时间复杂度

long long sum[100005];
long long solve(int n, int k, vector<int> &a){
    assert(a.size() == n);
    sum[0] = a[0];
    for(int i = 1; i < n; ++i) sum[i] = sum[i-1] + a[i];
    long long ans = sum[k-1];
    int p = 0;
    for(int i = k; i < n; ++i){
        long long x = sum[i]-sum[i-k];
        sum[p+1] = min(sum[p], sum[p+1]);p++;
        ans = max(ans, x);
    }return ans;
}