Falcão (falcao) wrote,
Falcão
falcao

задача дня -- 2

Вот не очень сложная задача, поэтому комменты я буду до некоторого времени "скринить".

Даю две формулировки условия. Сначала -- более "математизированная".

Дан массив целых чисел X[1..n]. Требуется найти максимум величины X[i]-X[j] по всем i<=j. Массив разрешается читать только один раз в режиме read-only. Дополнительная память состоит всего из нескольких ячеек (скажем, не больше пяти).

А вот более "занимательная" переформулировка.

Представим себе, что нам стала известна "инсайдерская" информация о курсе доллара на следующий месяц. Мы сидим у монитора, и на экране мелькают цифры -- не слишком быстро (чтобы мы могли проделать простейшие устные вычисления), но и не слишком медленно (записать на бумагу мы уже ничего не можем). Числа идут по дням, и они округлены до целого числа рублей (для простоты). Курс всё время колеблется. У нас есть некоторое количество баксов, и мы хотим наиболее выгодно их продать в один из дней, когда курс достаточно высокий, чтобы чуть позже купить их по подходящей цене, когда курс существенно снизится. Считается, что мы в каждый момент можем удерживать в голове несколько чисел (например, два или три). Требуется определить, на какую максимальную выгоду мы можем рассчитывать при такой сделке. Разницей между курсом покупки и продажи для простоты полагается пренебречь.

UPD (02.05) Раскрываю все комментарии. Спасибо всем, кто участвовал. По отдельности анализировать ответы не буду. Задача действительно была несложной, и все решения используют примерно ту же самую идею. В одном из первых же ответов прозвучало почти буквально то, что бы сказал я сам. Что касается длинных программных кодов, то я их, к сожалению, "не чтец" (для меня это примерно как читать "на чукотском" :)) Но из общих соображений было понятно, что там реализовано примерно то же самое (иногда почему-то длинновато).
Tags: задача-дня, математика
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 22 comments