Войти
или
Зарегистрироваться
Маркетплейс
Курсы
Учебник
Учебник 2.0
ЕГЭ
ОГЭ
Олимпиады
Рубрикатор
Компилятор
Онлайн Компилятор
Компилятор Python с отладкой
Питон - Черепашка
Эмулятор исполнителя Робот - Кумир
Редактор HTML Code
SQLite Studio - работа с БД
Клавиатурный тренажёр программиста
Олимпиадный тренинг
Задача
.
Максимальная сумма подотрезка. Тип К
Задача
Темы:
Информатика
Информатика
\(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]
1000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам
Кол-во
Python
93