\(A\) - вектор/список данных \(a_1,\ a_2,\ \cdots\ ,\ a_n \).
\(B\) - вектор "префиксных сумм" от\(A\) = \(b_0,\ b_1,\ \cdots\ ,\ b_n \ такой\ что: b_0=0, b_j=\displaystyle\sum_{i=1}^{j} a_i\)
Для заданного \(k \) "постройте" векто \(C\) =\(c_1,\ c_2,\ \cdots\ ,\ c_n \ такой\ что: \)
\(c_t=0,\ для\ t<k \\ c_t=max(\displaystyle\sum_{i=j-k+1}^{j} a_i \ |\ k\leq j\leq t)\)
Напишите фрагмент программы, выполняющую это "построение" используя значения вектора \(B\).
Программа должна возвращать список
| Пример для k=3 |
A
|
B
|
C
|
Пояснение |
[1,3,4,2,5,3,4,3]
|
[0,1,4,8,10,15,18,22,25]
|
[0,0,8,9,11,11,12,12]
|
1. Элементы списка C - неубывающая последовательность
2. C[0]=C[1]=0 так, как индексы меньше k
3.C[j]=max(B[j+1]-B[j+1-k],C[j-1])
так C[2]=max(B[3]-B[0],0)=8=A[0]+A[1]+A[2]
|