задача дня -- 2
Вот не очень сложная задача, поэтому комменты я буду до некоторого времени "скринить".
Даю две формулировки условия. Сначала -- более "математизированная".
Дан массив целых чисел X[1..n]. Требуется найти максимум величины X[i]-X[j] по всем i<=j. Массив разрешается читать только один раз в режиме read-only. Дополнительная память состоит всего из нескольких ячеек (скажем, не больше пяти).
А вот более "занимательная" переформулировка.
Представим себе, что нам стала известна "инсайдерская" информация о курсе доллара на следующий месяц. Мы сидим у монитора, и на экране мелькают цифры -- не слишком быстро (чтобы мы могли проделать простейшие устные вычисления), но и не слишком медленно (записать на бумагу мы уже ничего не можем). Числа идут по дням, и они округлены до целого числа рублей (для простоты). Курс всё время колеблется. У нас есть некоторое количество баксов, и мы хотим наиболее выгодно их продать в один из дней, когда курс достаточно высокий, чтобы чуть позже купить их по подходящей цене, когда курс существенно снизится. Считается, что мы в каждый момент можем удерживать в голове несколько чисел (например, два или три). Требуется определить, на какую максимальную выгоду мы можем рассчитывать при такой сделке. Разницей между курсом покупки и продажи для простоты полагается пренебречь.
UPD (02.05) Раскрываю все комментарии. Спасибо всем, кто участвовал. По отдельности анализировать ответы не буду. Задача действительно была несложной, и все решения используют примерно ту же самую идею. В одном из первых же ответов прозвучало почти буквально то, что бы сказал я сам. Что касается длинных программных кодов, то я их, к сожалению, "не чтец" (для меня это примерно как читать "на чукотском" :)) Но из общих соображений было понятно, что там реализовано примерно то же самое (иногда почему-то длинновато).
Даю две формулировки условия. Сначала -- более "математизированная".
Дан массив целых чисел X[1..n]. Требуется найти максимум величины X[i]-X[j] по всем i<=j. Массив разрешается читать только один раз в режиме read-only. Дополнительная память состоит всего из нескольких ячеек (скажем, не больше пяти).
А вот более "занимательная" переформулировка.
Представим себе, что нам стала известна "инсайдерская" информация о курсе доллара на следующий месяц. Мы сидим у монитора, и на экране мелькают цифры -- не слишком быстро (чтобы мы могли проделать простейшие устные вычисления), но и не слишком медленно (записать на бумагу мы уже ничего не можем). Числа идут по дням, и они округлены до целого числа рублей (для простоты). Курс всё время колеблется. У нас есть некоторое количество баксов, и мы хотим наиболее выгодно их продать в один из дней, когда курс достаточно высокий, чтобы чуть позже купить их по подходящей цене, когда курс существенно снизится. Считается, что мы в каждый момент можем удерживать в голове несколько чисел (например, два или три). Требуется определить, на какую максимальную выгоду мы можем рассчитывать при такой сделке. Разницей между курсом покупки и продажи для простоты полагается пренебречь.
UPD (02.05) Раскрываю все комментарии. Спасибо всем, кто участвовал. По отдельности анализировать ответы не буду. Задача действительно была несложной, и все решения используют примерно ту же самую идею. В одном из первых же ответов прозвучало почти буквально то, что бы сказал я сам. Что касается длинных программных кодов, то я их, к сожалению, "не чтец" (для меня это примерно как читать "на чукотском" :)) Но из общих соображений было понятно, что там реализовано примерно то же самое (иногда почему-то длинновато).