第一行：N, M
第二行：A[1], A[2], ..., A[N]
一个数字S，表示M次打菜的最大好吃程度之和
7 2 1 2 3 -2 3 -10 3
10
[1 2 3 -2 3] -10 [3]
7 4 1 2 3 -2 3 -10 3
12
[1 2 3] -2 [3] -10 [3]
第四次给机器人-1, -1的指令
N <= 10^5 = 100000
|A[i]| <= 10^4 = 10000
10%数据M = 1
50%数据M <= 2
80%数据M <= 100
100%数据M <= 10^4 = 10000
import copy n,m = map(int,input().split()) pre,d = [0] * n,[0] * n d0 = list(map(int,input().split())) d[0] = d0 [0] for i in range(1,n-m+1): #分一段 d[i] = max(d[i - 1],0) + d0[i] for i in range(1,m): #计算分m段，中间经过分2,3，..m-1段 pre = copy.deepcopy(d) max_j = max(pre[:i]) for j in range(i,i + n - m + 1): if j == i: d[j] = max(max_j,0) + d0[j] max_j = max(max_j,pre[j]) else: d[j] = max(max_j,d[j-1]) + d0[j] max_j = max(max_j,pre[j]) print(max(d))
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
