\(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 \) "постройте" векто \(D\) =\(d_1,\ d_2,\ \cdots\ ,\ d_n \ такой\ что: \)
\(d_t=0,\ для\ t>n-k \\ d_t=max(\displaystyle\sum_{i=j}^{j+k} a_i \ |\ t\leq j\leq n-k)\)
Напишите фрагмент программы, выполняющую это "построение" используя значения вектора \(B\).
Программа должна возвращать список
| Пример для k=3 |
A
|
B
|
D
|
Пояснение |
[1,3,4,2,5,3,4,3]
|
[0,1,4,8,10,15,18,22,25]
|
[12,12,12,12,12,10,0,0]
|
1. Элементы списка D - невозрастающая последовательность
2. D[-1]=D[-2]=0 так, как индексы ,больше -k
D[-3]=B[-1] -B[-4]=25-15=10=A[-1]+A[-2]+A[-3]
3.D[-j]=max(B[-j-1+k]-B[-j-1],D[-j+1])
так D[-4]=max(B[-2]-B[-5],D[-3])=
max(22-10,10)=12=A[-2]+A[-3]+A[-4]
|