k长连续子段和

[编程题]k长连续子段和

热度指数：1166 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个n个数字的序列 $a_1,a_2,\dots a_n$ ，你想知道所有长度大于等于k的连续子段中，子段数字和最大可以是多少。

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

示例1

输入

5,2,[-4,4,-2,1,-3]

输出

说明

因为要选的子段的长度必须大于等于2，所以最优的选择是选择[4,-2,1]，得到的答案为3

备注:

$2\le n\le 1e5, 1\le k\le n, -1e9\le a_i\le 1e9$

第一个参数n代表序列中的数字个数

第二个参数代表连续子段的长度要大于等于

第三个参数a包含个元素，代表给出的序列

算法知识视频讲解

Python

JackRyan

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:])

编辑于 2020-07-29 16:39:30 回复(0)