Нахождение максимального значения A [J] + - A [I]

Question

У меня на следующей неделе есть финалы, и я собираюсь пройти старые записи и домашние задания/экзамены, пытающиеся учиться. На моей второй домашней работе у меня есть вопрос, что я ошибся, и я просто не уверен, что именно делать. Вот проблема:

Разработка эффективных алгоритмов, которые принимают массив положительных чисел 'a', и определяют: a. максимальное значение a [j] + a [i], где j> or = to i. b. максимальное значение a [j] - a [i], где j> or = to i.

Мне не нужен фактический код, просто какой-то псевдокод и время его работы.

То, что я думал, что будет работать:

Найти первый, второй и третий максимум и минимум значений. Затем выполните: a. сначала max a (j) + second max a (i), для j> = i. b. сначала max a (j) - первый min a (i), для j> = i

А затем просто повторите со вторым max, min, если вышеописанное условие не работает.

Я не знаю, почему я не могу обмотать голову вокруг этого. Я знаю, что j может быть равным i, поэтому мой ответ даст неверный результат для части a. Для части b предположим, что у меня есть массив [89 | 90 | 1 | 2 | 3 | 4 | 5], он будет равен 90 - 1 = 89, но он должен быть 5 - 1 = 4. Я даже не пытался подумать о времени выполнения, поскольку эта часть ошибочна.

Любая помощь или подсказки были бы замечательными. Спасибо!

Answer 1

a. a [j] + a [i] является прямым, это всего лишь 2 * максимум, так как j может быть равным i, может быть сделано в O(N)

b. a [j] - a [i] для этого случая нам нужно немного динамического программирования, чтобы получить его в O (N). Вот способ сделать это в O (N): -

Создайте массив таким образом, что максимум [I] обозначает максимальный элемент в подмассиве в [я до п]

max[n] = a[n]   
for(i=n-1;i>=1;i--) 
    max[i] = maximum(max[i+1],a[i]); 

затем найти максимальное значение (max[i]-a[i]) для всех, которые будут вашими max a[j]-a[i].

Редактирование: Только что понял, что для поддержки массива max [] вы можете вычислить max [i] - a [i] при оценке max [i], используя только предыдущее значение.

Answer 2

a. до максимума a [i] + a [j] - найти наибольшее и второе по величине значение в массиве, это просто, а временная сложность - O (N).

b. Для максимума a [j] -a [i] (j> = i) для каждого j возможным оптимальным решением будет a [j] - минимальное значение перед j, поэтому вам просто нужно сохранить это значение и обновить наилучшее раствор

mmin = a[0]; 
ans = 0; 
for (int j = 0; j < length(a); ++j){ 
    mmin = min(a[j], mmin); 
    ans = max(ans, a[j] - mmin); 
} 
return ans; 

Это также O (N).