k长连续子段和

class Solution:
    def solve(self , n , k , a ):
        # write code here
        S = [a[0]]*n
        for i in range(1, len(a)):
            S[i] = S[i-1] + a[i]
        dp = S[:]
        for i in range(k, len(a)):
            dp[i] = max(dp[i-1] + a[i], S[i] - S[i-k])
        return max(dp[k-1:])

class Solution {
public:
    /**
     * k长连续子段和
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return long长整型
     */
    long long solve(int n, int k, vector<int>& a) {
        // write code here
        typedef long long ll;
        vector<ll> sum(n+1,0);
        vector<ll> dp(n+1,0);
        //构造sum数组
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+a[i-1];
        //dp从k开始，若i<k,第i个数字显然不能作为结尾
        dp[k]=sum[k];
        ll result=dp[k];
        for(int i=k+1;i<=n;i++){
            dp[i]=max(dp[i-1]+a[i-1],sum[i]-sum[i-k]);
            result=max(result,dp[i]);
        }
        
        return result;
    }
};

    solve(n, k, a: Array<number>) {
        let dp = new Array(n + 1).fill(0);
        let sum = 0;
        //先初始化
        for (let i = 1; i <= k; i++) {
            dp[i] = dp[i - 1] + a[i - 1];
        }
        let result = dp[k];
        for (let i = k + 1; i <= n; i++) {
            sum += a[i - k - 1];
            if (sum < 0) {
                //舍弃掉前半段，只留k个元素
                dp[i] = dp[i - 1] + a[i - 1] - sum;
                sum = 0;
            } else {
                dp[i] = dp[i - 1] + a[i - 1];
            }
            result = Math.max(dp[i], result);
        }
        return result;
    }