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

[falcao]

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

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

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

Comments

[ditour]

Помним X_max - максимальное до сих пор встреченное число - и D_max - максимальную разницу.
На первом шаге: X_max = Х[1], D_max = 0;
На i-ом шаге: X_max = max(X_max, X[i]), D_max = max (D_max, X_max - X[i])
На выходе D_max - требуемый результат.

[falcao]

У меня было в точности такое же решение (даже буквы для обозначений совпали :))

[palmas1]

Это про то, чтобы просматривая, запоминать max и min из увиденного, а потом вычесть?

"Математизированная" формулировка какая-то таинственная. Что такое режим read-only? И память - она к чему дополнительная?

[falcao]

Нет, первое явно не достаточно: может так оказаться, что максимум был 31-го числа, а минимум 1-го. То есть это максимум не по всем i,j, а только по i<=j. Продаём баксы в i-й день, когда курс высокий, потом покупаем, когда он снизился.

Режим read-only подразумевает, что мы не можем менять значения чисел массива по ходу дела. Он ведь представляет собой память, и я хотел исключить те решения, которые могут использовать большое число ячеек памяти. И те несколько ячеек, где мы что-то можем запоминать -- они дополнительные именно к этому массиву.

Формулировка, кстати, скорее "программерская".

[kotomord82]

Вроде бы просто
Храним найденный максимум (две ячейки - значение и признак "уже найден - еще не найден" : x, y = false)
Храним максимальное значение в прочитанном (аналогично - две ячейки X, Y= false)

Ну и для каждой прочитанной ячейки:
(значение - z)
if(Y){
if(y){
if(X-z > x) x = X-z;
}else{
y = true;
x =X-z;
}
if(X

[p_govorun]

Просматриваем массим последовательно, помним самое большое встретившееся число и самую большую разность. Каждый новый элемент массива сравниваем с запоненым максимумом (если больше -- заменяем), потом вычитаем его из запомненого максимума, если разность больше запомненной -- заменяем.

[roman_rogalyov]

Заведём ячейки a,b,r

Сначала сделаем так:
b:=X[1]
a:=X[1]
r:=a-b

а начиная с n=2 повторяем
a:=X[n]
r :=max(a-b,r)
b:=min(a,b)

результат в ячейке r