Вопросы и ответы
Топ за год Облако тегов  

Дан массив z[1], ..., z[W]. Найти a, b(a < b) такие что z[a] + ... + z[b] - максимальна.

программирование математика Наука алгоритмы задачи

Fearless, 174 просмотра
8
Количество операций должно быть порядка W.
Ответы:
xshmd-mgm
ничего сложного не вижу
nnexe
Мой алгоритм:
предлагаю воспользоваться методом динамического программирования. Заведем еще один массив x[1..w], где x[i] - это максимальная сумм  z[j]+z[j+1]+...z[i], для всех возможных j от 1 до i. Заполнять мы его будем следующим образом: x[1]:=z[1], для i>1: если x[i-1]>0, то x[i]:=x[i-1]+z[i], иначе x[i]:=z[i]. (итого W операций). Следующим шагом находим максимум из х[i] (еще W операций). Пусть j-индекс максимального элемента. тогда b:=j; и далее присваиваем i:=j начинаем идти вниз по 1-му, вычитая из x[j] поочередно z[i], пока x[j] не станет равно z[i], тогда a:=i; (не более W операций). Итог 3*W операций
nnexe
2 PetSerAl
действительно, не обратил внимания на строгость неравенства, ну тогда можно немного модифицировать правила заполнения массива x[2..w]. Пусть x[2]:=z[1]+z[2], далее , x[i]:=max(z[i-1],x[i-1])+z[i]


14 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.