Блог пользователя plagues

Можно ли решать такую задачу быстрее, чем за O(n^2)?
Автор plagues, история, 4 года назад, По-русски

Даны два массива равных размеров: a, b

Нужно для каждого x посчитать c[x] = max(a[j] + b[x — j]), для всех 0 <= j < x

a, b отсортированы

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

(max,+) convolution

→ Ответить